COMMENT ⊗   VALID 00037 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00005 00002	.DEVICE XGP
C00007 00003	.PORTION MACROS
C00010 00004	.NSEC(Abstract)
C00012 00005	.NSEC(Overview)
C00022 00006	.NSEC(Experts and BEINGs)
C00030 00007	.NSEC(Experts Interacting)
C00042 00008	.NSEC(The Program the Experts Wrote)
C00048 00009	.SSEC(Choice of Target Program)
C00056 00010	.NSEC(Anatomy of Synergetic Cooperation)
C00062 00011	.SSEC(Alternative Derivation of the Same Ideas)
C00072 00012	.SSEC(How to Build Such a System)
C00076 00013	.NSEC(Design Specifics)
C00084 00014	.SSEC(When a BEING Gains Control)
C00097 00015	.SSEC(Keeping the User Informed)
C00103 00016	.SSEC(Passing Control in the System)
C00117 00017	.NSEC(Theory of Pure BEINGs Systems)
C00133 00018	.NSEC(Experimental Results)
C00146 00019	.SSEC(The Range of Programs Synthesized by PUP6)
C00158 00020	.SSEC(Questions for Automatic Programming Systems)
C00172 00021	.NSEC(Conclusions)
C00177 00022	.SSEC(About Automatic Programming)
C00185 00023	.SSEC(About BEINGs)
C00192 00024	.ASEC(References)
C00200 00025	.ASEC(Appendix 1: Values of parts of a typical BEING)
C00211 00026	.ASEC(Appendix 2: The BEINGs present in PUP6)
C00221 00027		5B. Low-level, domain-specific knowledge*
C00235 00028		5D.  High-level, problem-independent knowledge: how to write
C00255 00029		5E.  Low-level  problem-independent   knowledge:   bits   of
C00267 00030		5F. Programming Knowledge stored in variables*
C00276 00031	.SSEC(The increment of knowledge necessary to write GI)
C00289 00032	.ASEC(Appendix 3: BEING usage data)
C00311 00033	.ASEC(Appendix 4:   Synthesized parts of CF program)
C00340 00034	.SSEC(Flow Chart of Target Program [CF]   including names of major functions)
C00345 00035	.ASEC(Appendix 5: Excerpts from the PUP6-User dialogue creating CF)
C00377 00036	\7This is the end of the example fragments of dialogue\*
C00398 00037	.EVERY HEADING(,,)
C00399 ENDMK
C⊗;
.DEVICE XGP

.FONT 1 "BASL30"
.FONT 2 "BASB30"
.FONT 4  "BASI30"
.FONT 5  "NGR40"
.FONT 6  "NGR25"
.FONT 7  "NGR20"
.FONT 8  "GRFX35"
.FONT 9  "FIX20"
.TURN ON "↑α↓_π[]{"
.TURN ON "⊗" FOR "%"
.TURN ON "@" FOR "%"
.PAGE FRAME 54 HIGH 89 WIDE
.TITLE AREA HEADING LINE 1
.AREA TEXT LINES 3 TO 53
.TITLE AREA FOOTING LINE 54
.COUNT PAGE PRINTING "1"
.TABBREAK
.ODDLEFTBORDER ← EVENLEFTBORDER ← 1000
.!XGPLFTMAR←110
.AT "ffi" ⊂ IF THISFONT ≤ 4 THEN "≠"  ELSE "fαfαi" ⊃;
.AT "ffl" ⊂ IF THISFONT ≤ 4 THEN "α∞" ELSE "fαfαl" ⊃;
.AT "ff"  ⊂ IF THISFONT ≤ 4 THEN "≥"  ELSE "fαf" ⊃;
.AT "fi"  ⊂ IF THISFONT ≤ 4 THEN "α≡" ELSE "fαi" ⊃;
.AT "fl"  ⊂ IF THISFONT ≤ 4 THEN "∨"  ELSE "fαl" ⊃;
.PORTION MACROS
.FILL
.SELECT 1
.MACRO B ⊂ BEGIN VERBATIM GROUP ⊃
.MACRO BB ⊂ BEGIN NOFILL SELECT 6 INDENT 0 GROUP ⊃
.MACRO E ⊂ APART END ⊃
.MACRO D ⊂ ONCE PREFACE 100 MILLS ⊃
.MACRO BBB ⊂ BEGIN  INDENT 0  PREFACE 100 MILLS  SPACING 45 MILLS ⊃

.MACRO NSECP(A)  ⊂  TURN ON "{∞→"   
.SSECNUM←0
.SECNUM←SECNUM+1 
.SEND CONTENTS ⊂
@1{SECNUM}. A⊗* ∞.→ {PAGE}
.⊃
.TURN OFF "{∞→"   
.SECTION←"A"
.NEXT PAGE
.ONCE CENTER TURN ON "{}"
@5↓_{SECNUM}. A_↓⊗*  
.  ⊃


.MACRO ASEC(A)  ⊂  TURN ON "{∞→"   
.SSECNUM←0
.SECNUM←SECNUM+1 
.SEND CONTENTS ⊂
@1A⊗* ∞.→ {PAGE}
.⊃
.TURN OFF "{∞→"   
.SECTION←"A"
.NEXT PAGE
.ONCE CENTER TURN ON "{}"
@5↓_A_↓⊗*  
.  ⊃


.MACRO NSEC(A)  ⊂  TURN ON "{∞→"   
.SSECNUM←0
.SECNUM←SECNUM+1 
.SEND CONTENTS ⊂
@1{SECNUM}. A⊗* ∞.→ {PAGE}
.⊃
.TURN OFF "{∞→"   
.SECTION←"A"
.GROUP SKIP 3
.ONCE CENTER TURN ON "{}"
@5↓_{SECNUM}. A_↓⊗*  
.  ⊃


.MACRO SSEC(A)  ⊂  TURN ON "{∞→"   
.SSECNUM←SSECNUM+1
.SEND CONTENTS ⊂
@7        A⊗* ∞.→ {PAGE}
.⊃
.TURN OFF "{∞→"   
.ONCE INDENT 6 TURN ON "{}"
@2↓_{SECNUM}.{SSECNUM}. A_↓⊗*  
. ⊃

.SECNUM←0
.PAGE←0
.NEXT PAGE
.TURN OFF "{"
.INDENT 0
.SELECT 1
.INSERT CONTENTS
.PORTION THESIS
.TURN OFF "{∞→}"   
.EVERY HEADING(⊗7{DATE}     D.  Lenat,BEINGs......section:  {SECTION},page {PAGE}⊗*)
.NSEC(Abstract)

	Knowledge may be organized  as  a
community  of  interacting  modules. Each module is granted
a complex structure, to simulate a particular expert in some small domain.
An extended analogy is drawn to a group of cooperating human specialists.
Based on this,
an internal constraint is imposed on the modules:
their structure  must be  standard  over  the  entire
community.
Some advantages  of  a  uniform  formalism are thereby preserved.
An  experimental  community was
designed  for  the task domain of automatic programming.
It has managed to synthesize 
a few inductive
inference  LISP  programs, nonformally,  from  specific  restricted
dialogues with a human user. 

.NSEC(Overview)
.PAGE←1

A group of human experts is able to function effectively because the diversity of
its members ensures a sufficient supply of fresh viewpoints and specific facts,
but also because its members think enough alike to communicate their needs and their
answers. For knowledge-based Artificial Intelligence programs, 
this suggests a partitioning of the
total knowledge into packets (each packet corresponding to a specialist), where
even though their contents are all unique, 
the internal structure of each packet is identical.
The dominant mode of interaction of the human experts is ⊗4questioning each other⊗*,
and the packets, called BEINGs, analogously have this ability. In fact, this is
just about the only thing that BEINGs ⊗4can⊗* do.
This whole analogy is drawn carefully in the opening sections of the memo.

To give the discussion substance, we fix the task -- of the experts and of the
BEINGs -- as the writing of an inductive inference LISP program.  A simulated
discussion among the humans eventually leads to the desired program; the problem
now reduces to building a BEINGs system which not only produces the same "target"
program, but whose questions and answers parallel those in the simulated dialogue.
Each BEING should correspond to one of the necessary experts, and should possess
enough knowledge to make the kind of responses which he made.

The BEINGs scheme
for representing knowledge is partially
realized in  an  experimental  system,  PUP6.
PUP6 has managed to synthesize three different
target programs:  a concept formation program (similar to [Winston]),
a grammatical inference program, and a simple information storage and
retrieval on keys system  
(referred  to  as, respectively, CF, GI, and  PL).
The BEINGs in PUP6 work by asking and answering
questions among themselves and with a distinguished entity called the User
(the sponsor
of the project).  While his role could conceivably be modelled by a BEING, it is
more natural to let the human using the system take his place. That is, whenever the
User must receive a question, it is typed out, and the human must type back a
meaningful (to PUP6) answer.

The actual dialogues, which serve to specify the desired target program,
are long and rigid. The user communicates in a miniscule
subset  of  English,  in  which  he delineates the task and discusses any
questionable details.  The  specification  is  partial (ambiguous):
the system makes assumptions continually. This is what is meant,
in the sequel, by ⊗4Automatic Programming.  Target program⊗* will refer
to code which has been successfully generated by such a system.
This will typically be written in the same language as the system itself.
⊗4Dialogue⊗* is the interactive communication between the human User and the
automatic programming system, which results in target code synthesis.
	Historically, the  CF  target  program  was first cleanly
specified. Next, an annotated
protocol was done
-- we simulated a meeting of human experts given the task of constructing a
concept formation LISP program. Each expert was then examined: the
knowledge he used throughout the dialgoue was collected and organized, then
embodied as a BEING.
In this way, the BEINGs modelled the simulated human experts, and were
able to reproduce  the  reasoning
present  in  the protocol. 
This pool of 100 BEINGs did eventually generate the desired CF program.
About a dozen new BEINGs were then added
to PUP6, and it was able to synthesize GI and INF.
	The  main  successes  of the experiment are that the desired
reasoning steps in the original protocol
were actually simulated, most of the BEINGs were used
in  writing  more  than one of the three generated programs, 
and the synthesized code
could be interrupted and asked a few kinds of  questions.   The  main
defects  were  the  inflexibility of the system to new dialogues, the
inability for  an untrained user  to  add  new,  high-level,  domain-specific
knowledge, the verbosity of the system,
and its ill-founded reliance on user infallability.
Some of these problems
may arise from the annotated protocol technique employed to  get  the
BEINGs  initially,  and  not  from  anything  inherent  to the BEINGs
representation.
	After motivating BEINGs with the human-experts analogy, we illustrate
details of their anatomy with examples taken from PUP6, and we illustrate their
interactions with examples of the PUP6-User dialogue which resulted in CF.
We next present details of PUP6 itself, including
a characterization of the dialogue between the human user and
the rest of the system, the range of programs synthesized by PUP6, and the
problems encountered. Our conclusions are of three varieties: those
which assess the BEINGs ideas, those relevant to PUP6's performance, and
a few observations about automatic programming.
	The conclusions about Automatic Programming arise because one may view this
research as falling in that field. It is a feasability demonstration, namely that
one ⊗4can⊗* automatically synthesize large, 
sophisticated programs, tens of pages long, involving
hours of user-system interactions. 
Many of the assumptions which are reasonable when concentrating upon tiny targets
become limiting factors in large dialogues. These lead to new difficulties which
the "next generation" of informal automatic program synthesis systems must face.
	The  appendices  present  further   details,   samples,   and
examples.   First  comes  a dissection of one BEING present in PUP6.
Appendix  2  summarizes the knowledge present in each BEING in the system.
Next comes a table  of data recording how the BEING community interacts.
Appendix 4 contrasts pieces of the synthesized CF program against their hand-coded
counterparts. The final
appendix presents  excerpts  from  the User-PUP6 dialogue as it synthesizes CF.

.NSEC(Experts and BEINGs)

Consider an interdisciplinary enterprise, attempted by a community of human
experts who are specialists in -- and only in -- their own fields.  What modes of 
interactions will be productive?  The dominant paradigm might well settle into
⊗4questioning and answering⊗* each other.
Instead of a chairman, suppose the group adopts rules for
gaining the floor, what a speaker may do,  and how to resolve disputes.
When a topic is being considered, one or two
experts might recognize it and speak up. In the course of their exposition
they might need to call on other specialists. This might be by name, by specialty,
or simply by posing a new sub-question and hoping someone could recognize his own
relevance and volunteer a suggestion.  Such transfers would be more common at
the beginning, when the task is (by assumption) too general for any one member to
comprehend.  As the questions focus on more specific issues, single individuals
should be able to supply complete solutions.
If the task is to construct something, then the
activities of the experts should not be strictly verbal.  Often, one will 
recognize his relevance to the current situation and ask to ⊗4do⊗* something:
clarify or modify or (rarely) create.

What would it mean to ⊗4simulate⊗* the above activity?  Imagine several little 
programs, each one modelling a different expert. What should each program,
called a ⊗4BEING⊗*, be capable of?  It must possess a corpus of specific facts and
strategies for its designated speciality. It must interact via questioning and
answering other BEINGs. Each BEING should be able to recognize when it is relevant.
It must set up and alter structures, just as the human specialists do.

Let us return to our meeting of human experts.
To be more concrete, suppose their task is to design and code a large
computer program: a concept formation system[Hempel; Winston]. 
Experts who will be useful
include scientific programmers, non-programming psychologists,
system hackers, and management personnel.
What happens in the ensuing session?  When an expert participates, he will
either be aiding a colleague in some difficulty
or else transferring a tiny, customized 
bit of his expertise (facts about his field) into a programmed function
which can do something.  The final code reflects the members' knowledge,
in that sense.
One way the session might proceed is for the specialists to actually ⊗4do⊗*
the concept formation task. As they become familiar with what part of their own
expertise is being called upon, and in what ways, they can begin to isolate it.
When it is clear precisely what each is doing, they can take their extracted
bits of knowledge,
organize them,
formalize them, and program them.  {A conscious
effort along these lines was made in [Woods], where experts gradually replaced
themselves by programs.  Instead of discussing how to write a speech program,
they ⊗4did⊗* speech recognition, until each one could introspect sufficiently
into his own activities to formalize them.}  For our task, one expects the
psychologists to dominate the early discussions, later yielding to programmers.
The project sponsor might be passive, submitting a single specification order for
the program, or active, participating in the work as a (somewhat priveleged) member
of the team. This individual is the one who wants the final product, hence will be
called the ⊗4user⊗*.

How could BEINGs do this? There would be some little program containing information
about ⊗6CONCEPT-FORMATION⊗*
(much more than would be used in writing any single concept formation program),
another BEING who knows
how to manage a group to
⊗6WRITE-PROGRAMS⊗*, and many lower-level specialists, for example 
⊗6INFO-OBTAINER, TEST, MODIFY-DATA-STRUCTURE, UNTIL-LOOP, 
VISUAL-PERCEPTION, AVOID-CONTRADICTION, PROPOSE-PLAUSIBLE-NAME⊗*.
Like the human specialists,
the BEINGs would contain far too much information, far too
inefficiently represented, to be able to say "we ourselves constitute
the desired program!"
They would have to discuss, and perhaps carry out, the concept formation task. They
would write specialized versions of themselves, programs which could do exactly what
the BEINGs did to carry out the task, no more nor less (although they would
hopefully take much less time, be more customized).
This activity is referred to in the sequel as ⊗4automatic programming⊗*.
Some BEINGs 
(e.g., ⊗6TEST⊗*) may have several
distinct, streamlined fractions of themselves in the final program. BEINGs which
only aided other BEINGs (e.g., ⊗6PROPOSE-PLAUSIBLE-NAME⊗*)
may not have ⊗4any⊗* correlates in the final
synthesized code.

The next section illustrates how the experts might have cooperated on the task
of writing the concept formation program. Section 5 describes the program they
produced. Next comes the BEING hypothesis: complex but standard
anatomy.  Later sections explain this, both theoretically and by examining
the behavior of the actual PUP6 pool of BEINGs.

.NSEC(Experts Interacting)

The input/output behavior of the desired concept formation program
is specified in this section, and we eavesdrop on a simulated
group of specialists  as they get to work on writing it.
As the presentation of the experts' activities
becomes more specific, the reader's currently vague
conception of BEINGs 
will be made less amorphous (because BEINGs are constrained to carry on
approximately the same discussion as the experts below do).

Externally, the concept formation task can be specified as follows: pictures of
structures (built out of simple geometrical shapes) will be presented one after
another. For each such scene, 
the concept formation program, call it CF, must guess its
name. The presenter will then reveal the correct name of the structure. CF
must quickly
learn to identify simple structures (ARCH, TOWER), and must
never make the same mistake
twice in a row.

Our group of experts are given this specification for CF. Assume that the user
(the financial sponsor) is available for resolving important 
questions, via messenger, and he may in fact
ask questions of the group.  
Whenever an expert speaks, almost all the others in the room hear him. Usually
only a few can benefit from what he says, and fewer still care to react.
The conversation in the room might go something like
the following (the suggestive names of the experts are of course coincidental):

.BBB

GENL-MANAGER: Can anybody here figure out what to do, what the user's saying? (waves
the input/output specifications in the air)

PGM-MANAGER: I can. He wants a computer program to be written. If somebody will
explain the task "con-cept-for-ma-tion" to me a little clearer, 
I'll delegate it properly.

PSYCH: Permit me to assist you. I know all about concept formation.
In fact, my master's thesis...

PGM-MANAGER: Wait, let me tell the user that we'll be able to handle the job.

MESSENGER: Here, I can take that message. Go on with your work.

PGM-MANAGER: We need a name for this program. Somebody get one, please.

NAMER: How about "CONCEPT"? Maybe just "CF". Let's ask the user to decide.

MESSENGER: (panting) I just came back from there! Alright, I'm going...
User says to call it CF.

PGM-MANAGER: Now then, I have four people in mind, one of whom must take over 
now in an important way. Each of them always wants to do something different.

CHOOSER: Give me their names and I'll choose the best one for you.

PGM-MANAGER: They are INFO-OBTAINER, INFO-USER, PGMMER, and ANALYST.

CHOOSER: You four experts each must justify to me why 
you should take control now.
.BEGIN INDENT 3

INFO-OBTAINER: We already have some unused information, so I guess I can wait.

INFO-USER: Let me have the floor! I know what to do with the user's specification.

PGMMER: Well, I suppose I could set up some "empty" top-level function, er...

ANALYST: Marginal profits accruing from my working at this point in 
time do not warrant...
.END

CHOOSER: Okay, INFO-USER, you seem to be the only relevant expert.

INFO-USER: First thing is for PSYCH to tell us how to actually ⊗4do⊗*
concept formation.

PSYCH: There are several decisions to be made, depending on what your independent
variables and your experimental setup are. For example, are we studying one 
individual, or must our program adapt to simulate many different subjects? Must
stimulus items be just classified, or classified and ordered, 
or classified and ordered and
metrized? Are the scenes left in view indefinitely, or just the current scene, or is
even that one just flashed before the subject for a limited time? May the subject
make written notes? 
Can he learn from positive instances of the concepts?
from negative instances?
Is there to be any positive transfer effect...?

DEFER: Hold on here; we can't swamp the user with lots of unnecessary questions.
Let's go through each one and see if it can wait.
Consider the  decision about the task being classificatory, comparative, or
metrical. What is the first situation in which we really use the result of that 
choice?

WHEN-NEXT: This involves a list of alternatives. Who knows about that?

ALTERNATIVES: I know a few tricks here. If all the alternative sequences
of activities have the same initial subsequence, then do that common
subsequence before making the decision.

UTILIZE: In this case, all three begin by partitioning a domain of elements.

DEFER: Temporarily, replace the task CF by the task of partitioning a domain.
Now consider the decision about subject-specific behavior being required.

PSYCH: This involves periodically inputting a description of the human subject.

CODER: That would mean adjusting the algorithms based on a vector of parameters.

WHEN-NEXT: This would probably affect the entire code. 

DEFER: I can't defer this decision. Someone had better take care of it.

RESOLVE: Ask the user about it.

ASK-USER: Phrase this as a yes/no question. Explain each alternative to the user.

MESSENGER: That's my job... User says no, don't simulate different people.

DEFER: The next decision... 

  
⊗4Eleven decisions are ultimately proposed by PSYCH, and all but one are deferred.⊗*

INFO-USER: I have no objections now if someone wants the floor.

PGM-MANAGER: Do any of the other three experts I mentioned earlier want
to speak now?

PGMMER: Yes. The top-level function CF can now be coded.

CODER: Give me the arguments and the body of the code, please.

PGMMER: There are no known arguments. The body is a call on ⊗4PARTITION-DOMAIN⊗*.

CODER: Okay. I will precede that with a call to an ⊗4INITIALIZE⊗* function,
and follow it
with a call to a ⊗4FINALIZE⊗* function, which are both defined as NIL for now.
Is ⊗4PARTITION-DOMAIN⊗* simple enough to be composed right now and filled in here?

MATHEMATICIAN: No way. While conceptually elegant in its simplicity, 
any realizate...

CODER: Uh, thanks. There. The function CF is defined as

.ONCE INDENT 6
⊗6(LAMBDA ( ) (INITIALIZE) (PARTITION-DOMAIN) (FINALIZE)).⊗*

ANALYST: Remind me to examine the initialization and finalization functions at the
end of our task. If either function is still null, it will be deleted.

WARNER: I have just put that note into the code for CF, as a comment.

PGMMER: Can someone advise me of what else to do to finish defining this function?

PGM-MANAGER: Each function should have a proper name. Show the user the names you
have picked, and let him choose other ones if he prefers.

MESSENGER: Okay...  The user agrees to all three names for the function calls.

INFO-USER: Somebody, please tell the group 
how to ⊗4do⊗* partitioning of a space of examples.
.END
A complete script, like the above, was constructed by hand.
In the sequel, this will be referred to as the ⊗4protocol⊗*.
In all, 87 different experts were called for: 17 specificly dealing with
inductive inference tasks, and 70 dealing with programming, managing workers,
and communicating with the user.
Near the end of the protocol, the user is asked which of the three types of concept
formation CF is supposed to do. He responds "⊗4CLASSIFICATORY only⊗*", and the
experts discover that they are finished. All the newly created code is dumped
out onto a fresh file:
After hundreds of pages, a
concept formation program meeting the user's specifications had been written.
The next section will describe that program in detail.

.NSEC(The Program the Experts Wrote)

One of the experts at the simulated
meeting must have read P. Winston's dissertation[Winston],
because CF, the synthesized concept formation program, was remarkably similar to
the one therein described. 
CF has a much simpler graph-matching algorithm, and relations on relations
are stored in a different way than simple relations on objects.
Since CF was later synthesized by PUP6, the
programmed pool of BEINGs, it is worth detailing here.

CF repeatedly scans a scene and tries to name it. As a first step, the scene
is broken into a set of objects and a set of features (relations on those
objects). Internally, CF maintains a model for each differently-named scene it has
encountered. A model contains a description of the objects one expects in
such a structure, a set of features which ⊗4must⊗* be present in any scene
having this name, a set of feature which ⊗4must not⊗* be present if the scene
is to have this name, and a set of features which ⊗4may⊗* be present or
absent. Thus a model is an archetypical scene plus a name.
For example, part of a scene might be:     
.B
	OBJECTS a,b,c,d
	RELATIONS  (GREEN a) (BLUE c) (TOUCHES c d) (SUPPORTS a c) (SUPPORTS b c)

CF's current model for an arch might be:      	   
	NAME    ARCH
	OBJECTS a,b,c
	MUST 	(SUPPORTS a c) (SUPPORTS b c)
	MUSTNOT (TOUCHES a b)
	MAY	(GREEN a) (WEDGE c) (PRISM a) (BLOCK b) (PARALLEL a b)
.E

Each time it is confronted by a new scene, CF  must
scan its models until it finds one which matches it. A model is said
to match a scene if all the MUST features associated with that model
are observed in the scene, and all the MUSTNOT  features  are
absent  from  the   scene. CF
informs the user of this guess,
and accepts the proper  name. If it  guessed  incorrectly,  it
modifies its models. The wrong-guess model may have features added to
its MUST or MUSTNOT sets.  P. Gadwa showed this is sufficient to
prevent CF from making the same wrong guess twice in succession.
The correct-name model may have  to
be  modified or (if it's a new name) created and inserted into the
list of models, to ensure that CF will eventually learn that concept.
The genesis of the idea of a MUST/MUSTNOT/MAY division is simulated
in Section 7.4.

	Suppose  that the target program reads in the above
scene fragment and
tries to match it to  the  above  ARCH model.  The  MUST
relations  should  all  be  present.   Yes,  the  scene  does contain
(SUPPORTS a c) and (SUPPORTS b c). Next, the MUSTNOT  relations  must
be absent from the scene. Sure enough, (TOUCHES a b) isn't there.  So
the model and scene are consistent, and the program announces that its
guess is ARCH.  
If the user verifies this guess,
then  the MAY set of the ARCH model
is augmented with the relations (BLUE c) and (TOUCHES c d), and
the OBJECTS set is augmented with "d."
	If the user denies that the scene is an arch, CF
sees if there are any relations in the ARCH model's MAY set which do not
occur in the scene. If so, one of them (e.g., (PARALLEL a b)) will
be transferred from the MAY to the MUST set.  If no such feature 
existed, the program would look for a feature present in the scene
but not mentioned in any set of the ARCH model (e.g., (TOUCHES c d)), and insert
it into the MUSTNOT set.  In either case, the user would
be asked what the true name was, and that
model would have its MAY set augmented by any new 
features in the scene. Any features on  the true-name model's
MUST or MUSTNOT sets
which contradicted the scene would be transferred to the MAY set.

.SSEC(Choice of Target Program)

The selection of a sophisticated program like [Winston] as the target was based
on earlier research; those uninterested may freely skip to the next section.

	Once  the  task  (automatic  program  synthesis from specific
dialogue) was decided  upon,  considerable  attention  was  spent  on
choosing  an  appropriate  ⊗4domain⊗*  of  target  programs.  The choice,
inductive inference, merits  discussion.  The  obvious
difficulty  appears  to  be  the complexity of the programs involved:
they  are  two  orders  of  magnitude  larger  than  any   previously
automatically synthesized  programs. But there are four big attractions:
	(i)
A  wide  range  of  complexity  exists,  from  a  one-page   sequence
extrapolator   to   Meta-Dendral.
	(ii)   Each   increasingly
sophisticated Inductive Inference program  uses  many  of  the  
concepts  embodied  in
simpler  Inductive Inference programs.
	(iii) If a super-human target program is
ever written, it could itself contribute to the  field  of  Automatic
Programming! (This remark is humorous in the seventies, but may be
commonplace someday.)
	(iv)  Since people (especially those who write
AI  programs) are the inductive
inference experts, our reliance on  introspection  is  as
valid  --  and potentially as valuable -- as chemists' protocols were
to Dendral.
	After  studying  many  sample  programs  from  the II domain,
sequence extrapolation [Pilvar] seemed the most reasonable  beginning
task. It was quickly learned that this was too easy: humans have only
a few techniques for extrapolating  sequences,  and  a  very  limited
capacity   for   composing   them.   Thus  a  rather  rigid  sequence
extrapolator writer may be capable of generating  a  large  class  of
super-human programs (see section 4.2 on
Sequence-Extrapolator-Writer, in [Green]).
	The  next  candidates  were grammatical inference and concept
formation [Hempel].
Determined not to choose too simple  a  task  again,  the
latter program was finally decided upon.

	After the target concept formation program was specified,  it
was trimmed and then rewritten as a structured program [Gadwa]. Next,
a complete dialogue was  simulated  between  the  user  and  a  human
programmer  (referred to as the system-player) playing the role of an
"intelligent"  automatic  programming  system  (similar   to,   e.g.,
[Balzer]).      The   system-player   kept   careful  records  as  he
programmed, and tried to create a bug-free  structured  program.  The
dialogue  was  then annotated:     after each user response, comments
were inserted which described the "states" the system-player had gone
through before printing his next response.  This included blind paths
which were tried, use of outside world knowledge,  and,  in  general,
was  meant  to  be  the "intelligence" necessary to do the task.  The
fear was that a system could be built which synthesized  the  concept
formation  program,  and  yet  was  so unintelligent that nothing was
learned from it. (see section 4.1 on PW1, for example,  in  [Green]).
	Hopefully,  any  system  which  
(i) got the target program correctly,
(ii) followed this
initial dialogue, and, most importantly, (iii) went
through  the  same  line of reasoning that the comments indicated the
system-player 
followed, would have to be doing ⊗4something⊗* right.  A
corollary of this incremental annotated protocol approach is that the
abilities of the user must coincide with those  of  the  subject  who
participated  in the protocol (see also [Woods]). The system would be
far along the road toward automatic programming if it also  (iv)  were
able  to  write  CF  from several dialogues, from several users, with
little preparation. PUP6 was not designed to do this, and in the  end
it  proved to be a serious deficit.  Henceforth, ⊗4protocol⊗* will
refer to this user-player / system-player simulated dialogue.

	At  this  point,  most  of  the  ideas about BEINGs
surfaced, including a rough initial set of BEINGs.  Each one had  not
much  more  than  a  name and a vague description of what it must do.
The  dialogue  was  cycled  through  again,  painstakingly,  and  the
comments  were  replaced  by a description of which BEINGs would call
which other BEINGs, why, and the results  of  each  such  call.   The
constraints   on   each  BEING  thus  grew,  sometimes  changed,  and
occasionally a new BEING or  BEING  part  had  to  be  added  to  the
community.  This  process  was  long  (200 hours) and produced a long
(200-page) protocol, actually a hand trace of the  system  execution.
About  eighty  BEINGs  were needed:  a dozen domain-specific ones and
the rest  domain-independent  programming  knowledge.
The major decision remaining was how to organize each module of knowledge,
how to encode each BEING. To answer this, we turn again in the next section
to our human experts analogy.

.NSEC(Anatomy of Synergetic Cooperation)

Consider the birth of one small idea necessary in the writing of CF,
that of classifying a model's features into three categories
(MUST, MUSTNOT, MAY). Later, this genesis will be presented, 
as if the group of experts were discussing it. 
No single specialist at the meeting could have had this idea by himself.
How do intellects mesh, 
effectively communicate, and unite their powers?
A tentative mechanism, which barely scratches the surface of this mystery, will
be hypothesized. The BEINGs in PUP6  embody this
concept, and are able to reproduce both the experts' discussion and
the actual working CF program.

Viewing the group of experts as a single entity, what makes it
productive? The members must be very different in abilities, in order to handle
such a complex task, yet similar in basic cognitive structure 
(in the anatomy of their minds) to
permit facile communications to flow.
For example, each specialist knows how to direct a programmer to do
some of the things he can do, but the specific facts each expert has
under this category must be quite unique. Similarly, each member may have
a set of strategies for
recognizing his own relevance to a
proposed question, but the ⊗4contents⊗* of that knowledge varies from
individual to individual.  The hypothesis is that all the experts can be
said to consist of categorized information, where the set of 
categories is fairly standard, and indicates the ⊗4types⊗* of questions
any expert can be expected to answer. An expert is considered ⊗4equivalent⊗*
to his answers to several standard questions.
Each expert has the same mental "parts", it
is only the values stored in these parts, their contents,
which distinguish him as an individual. 

Armed with this dubious view of intelligence, let us return to the design of
BEINGs. Each BEING shall have many parts, each possessing a name (a question it
deals with) and a value (a procedure capable of answering that question).
Henceforth, "⊗4part⊗*" will be used in this technical sense.
When a BEING asks a question, it is really just one
part who is asking. In fact, it must be that the ⊗4value⊗* subpart of some part
can't answer ⊗4his⊗* question without further assistance. He may not know
enough to call on specific other
BEINGs (let anyone respond who feels relevant), but
he should ⊗4always⊗* specify what BEING ⊗4part⊗* the question should be answered by.
By analogy with the experts, each BEING will have the same "universal" 
set of types of parts (will answer the same kinds of queries), and this uniformity 
should permit painless intercommunication. Since the paradigm of
the meeting is questioning and answering, the names of the parts should
cover all the types of questions one expert wants to ask another. Each part of
each BEING will have implicit access to this list: it may ask only these
types of questions. Each BEING should ⊗4not⊗* have access to the list of all
BEINGs in the system: requests should be phrased in terms of what is wanted;
rarely is the name of the answerer specified in advance.
(By analogy: the human speaker is not aware of precisely who is in the room;
when he feels inadequate, he asks for help and hopes someone responds).
Another point is that BEINGs are not a recursive concept (like ACTORs[Hewitt] are):
a part of a BEING is a brief collection of knowledge (usually 
a little LISP program), not
another BEING; a collection of BEINGs (also called a community, a pool,
the system, or a group)
is also not itself a BEING. There are no ⊗4structured⊗* clusters of BEINGs.

.SSEC(Alternative Derivation of the Same Ideas)


There is another route to approach this whole issue of viability, which we
shall briefly digress along.
Despite the awesome physical forces affecting Earth (weather, gravitation,... ),
it is ⊗4biological⊗* entities
who dominate our planet.  Much of science and philosophy are aimed at 
observing and explaining this mystery.  One approach to Artificial Intelligence
is to assume that Man "works," then try to model his attributes in a mechanical
device (or, equivalently, in a computer simulation). This paper describes one
such project. We shall begin by extracting the most obvious characteristics of
living organisms, especially of Man, and then design a program which incorporates
them.

Perhaps the most obvious distinction between, e.g., Weather and Animals, is that
of ⊗4discreteness⊗*. Yet besides  having distinguishable boundaries, each
species has a specific ⊗4anatomy⊗*. That is, each such creature is alike in
many important functional, physiological, structural, and psychological respects.
More than uniformity is required; the grains of sand in a desert fit our description
as it now stands. 
⊗4Individual abilities⊗* must be recognized; despite their similarity,
each member of a species is slightly different in his perception of
features of his environment, in his responses to those features, 
in his drives, and in his
capabilites. In many species, including humans, this has been carried to the extreme
of ⊗4professions.⊗* Each individual has an occupation, a specialty. A collection
of diversified experts is more viable than a similar collection of generalists.

So we limit our attention to  a community of discrete entities, 
sensitive to the world around them, each with his own distinct
expertise, yet all anatomically and psychologically similar.
How do they ⊗4interact⊗* in a meaningful, productive manner? 
Biology would lead us to hypothesize ⊗4competition⊗*, but 
perhaps the key is
⊗4cooperation.⊗*  Specialization is of advantage only if each specialist is willing
to use his talent to serve the entire community. In part this may be instinctive,
but much of Man's supremacy stems from learning to cooperate. The institutions
of the law, education, and government universally reflect (distortions of) this
ideal. 
Advancement ⊗4within⊗* a society may be by competition, 
but advancement ⊗4of⊗* a society
necessitiates synergy.
But how do people help each other; what is the "mechanism"? 
Perhaps it lies in ⊗4communication⊗*. This has three aspects: 
(i) broadcasting your own needs to the specialists who might help you, or to the
entire community; (ii) recognizing
when you are relevant to satisfying someone else's specific need; (iii) satisfying
that need, often by posing new sub-requests to the community.

Besides communication, another constructive process of living 
entities is ⊗4reproduction.⊗*
The organisms combine, usually in small groups, and produce a new, similar being.
Heredity ensures that he will be somewhat similar to his parents, yet not identical.
The father teaches the son his trade; perhaps the offspring becomes even more of
a specialist in that field; perhaps he becomes more versatile by integrating
lessons learned from several of his ancestors.
We shall therefore assume that our entities can ⊗4reproduce and teach their 
progeny⊗*.

These characteristics are now ⊗4postulated⊗* as constraints on the computer
simulation we wish to construct. The program will be made up of discrete modules,
which we have called BEINGs, each possessing a clump of specialized knowledge.
Each BEING shall have the same internal structure, can respond to the same kinds
of questions (though with different answers in each case). The only things that
a BEING can do are: broadcast a plea for assistance, recognize his own ability to
help in a certain situation, provide the needed answer in such cases, combine
with  0,1, or 2 other BEINGs to produce a new BEING, and teach that offspring
some of what it knows.

The reader may protest that much has been ignored: primitive drives, 
instincts, emotions,
aesthetics, ethics,...  Some of these may be dealt with in the proposed
continuation of this project,
a system which can make simple mathematical discoveries.
Such a system must have a sense of aesthetic beauty, harmony, innate interestingness,
as well as a sense of intuition, instinct.
It is not felt that the complexity of human emotions is 
prerequisite to intelligence;
BEINGs need not simulate emotions.  
No case shall be argued in favor of these
prejudices; rather, we shall test them, observing what happens
in a system which assumes them. 
Before discussing that attempt,
let us formally define some of our terms.


A ⊗4system⊗* of BEINGs, also called a ⊗4pool⊗*,
is a collection of knowledge modules, plus
auxilliary support functions (like "Pattern-match", "Sort"). A
⊗4BEING⊗* is nothing more than a collection of about thirty parts.
Each ⊗4part⊗* of BEING B is an ordered pair ⊗2(q,a)⊗*, where
⊗2↓_q_↓⊗* is an abbreviated name of a question, and ⊗2↓_a_↓⊗* is a
program which can be run to provide B's answer to ⊗2↓_q_↓⊗*. In the
course of executing ⊗2↓_a_↓⊗*, new questions may be raised, new
BEINGs may be created, parts of existing BEINGs may be changed, and
messages (hopefully including the desired answer) may be passed. 

Once again: the concept of a pool of BEINGs is that many specialized 
entities coexist, each
having a complex structure, but that structure does not vary from entity to entity.
This idea has analogues in many fields: transactional analysis in
psychology, anatomy in medicine, modular design in architechture.

.ONCE TURN ON "[]"
It seems that ⊗2Q = {q}⊗* might need to be immense, to cover all the kinds of
queries any expert might ever want to put to another expert. In fact,
in order to make ||⊗2Q⊗*|| manageably small, it is necessary to restrict the
task domain of the BEINGs system. For example, a set Q↓c↓f of
30 parts can be found which suffice to discuss concept formation, and a
set Q↓[math] of 30 which suffice to discuss mathematical research, but those two
sets are almost disjoint.

.SSEC(How to Build Such a System)

How can we test out this idea? We must build a pool of BEINGs, a modular program
which will interact with a human user and 
do some specific task (like write the CF program).
Recasting the idea into operational terms, we arrive at this procedure for
constructing a pool of BEINGs: 

.BEGIN INDENT 0,4,0

(1) Study the task which the pool is to do. See
what kinds of questions are asked by (simulated) experts, as they cooperate to
carry out that task.

(2) Distill this into
a core of simple questions, ⊗2Q⊗*,
in such a way that each inter-expert question or transfer
of control can be rephrased in terms of some ⊗2↓_q_↓ ε Q⊗*.
The size of ⊗2Q⊗* is very important.
If Q is too large, addition of new
BEINGs will demand either great effort or great intelligence (an example of a
system like this is ACTORS [Hewitt]). 
If Q is too small, all the non-uniformity is simply
pushed down into the values of one or two general 
catchall questions (all first-order
logical languages do this). 

(3) List all the BEINGs who will be
present in the pool, and fill in their parts. 
The time to encode knowledge into many simple representation schemes is
proportional to the square of (occasionally exponential in) 
the amount of interrelated knowledge (e.g., consider the frame problem).
The filling in of a new BEING is  ⊗4independent⊗* of
the number of BEINGs already in the pool, because BEINGs can communicate
via nondeterministic goal mechanisms, and not have to know the names of the BEINGs
who will answer their queries. This filling in is  ⊗4linear⊗* in the number of
BEING parts listed in Q; all parts of all BEINGs must be (at least, should be)
filled in.

(4) The human user interacts with the completed
BEING community, until the desired task is complete.

.END

In section 7, we carry out this programme for the task of generating CF automatically.
The gain from constraining
Q to be constant (over all the BEINGs in the system)
will be clarified. Theoretical aspects of BEING systems follow,
in section 8. 
Next comes an evaluation of PUP6's behavior.
The uses and the problems with BEINGs are summed up in the final section.

.NSEC(Design Specifics)

.SSEC(The parts of a BEING)

After simulating a complete meeting of cooperating experts writing CF,
all the 10000 questions they asked were examined and partitioned into
29 classes of inquiries. In this way, PUP6's
set of 29 ubiquitous questions were chosen, representing everything one
expert might want to ask another. 
At least, they naturally encompass those questions which were asked during the
simulated meeting, hence should be sufficient for generating CF.
⊗2Q⊗*, this
universal set of BEING parts, is listed in the box below.

Many experts, though needed during the session, did not have to answer
all 29 classes of questions sometime during the dialogue, in order for CF to be
correctly synthesized. These BEINGs therefore didn't need all their parts filled
in; alternatively, each part was really present only for ⊗4some⊗* of the BEINGs
in PUP6; alternatively, if all parts of all BEINGs were really filled in, there would
be a vast amount of needless information, superfluous facts, unused code.
The percentage of the experimental pool  of BEINGs
which actually needed each part (so that PUP6 could
generate CF) is noted in the box below.

.XGENLINES←XGENLINES-3
.BEGIN NOFILL GROUP  PREFACE 0 MILLS  WIDEN 0,3  TURN ON "→∞"  SELECT 8
.ONCE TURN OFF "α"
⊂∞α→⊃
.SELECT 6
⊗8~⊗*						⊗2↓_BEING Parts_↓⊗* →⊗8~⊗*
⊗8~⊗*⊗2WHAT⊗* 82%  A brief summary of the global purpose, a template for an English phrase.→⊗8~⊗*
⊗8~⊗*⊗2WHY⊗* 77%  A justification of the BEING's existence, partly filled in by the BEING who called it.→⊗8~⊗*
⊗8~⊗*⊗2HOW⊗* 72%  A summary of the methods the BEING intends to employ. Global strategies.→⊗8~⊗*
⊗8~⊗*⊗2IDEN⊗* 54%  How this BEING is referenced in English phrases. Implemented as productions.→⊗8~⊗*
⊗8~⊗*⊗2WHEN⊗* 19%  Why this BEING should be given control now. The sum of weighted factors.→⊗8~⊗*
⊗8~⊗*⊗2ARGS⊗* 63%  Number of arguments; which are optional; names of any local variables.→⊗8~⊗*
⊗8~⊗*⊗2ARG-CHECK⊗* 81%  Predicates which examine each argument for suitability.→⊗8~⊗*
⊗8~⊗*⊗2EVAL-ARGS⊗*  4%  Which arguments are to be evaluated, and which quoted.→⊗8~⊗*
⊗8~⊗*⊗2REQUISITES⊗* 10%  If this BEING is actually chosen, what must be made true prior to (pre)→⊗8~⊗*
⊗8~⊗*		during (co), and after (post) execution.  Work to make these true (unlike ARG-CHECK).→⊗8~⊗*
⊗8~⊗*⊗2DEMONS⊗* 7%  Set of demons to be kept active while the BEING is in control.→⊗8~⊗*
⊗8~⊗*⊗2INHIBIT-DEMONS⊗*  5%  A lock/unlock mechanism, useful when handling demonic interrupts.→⊗8~⊗*
⊗8~⊗*⊗2EFFECTS⊗* 27%  What will probably be true after this BEING is through. What it achieves.→⊗8~⊗*
⊗8~⊗*⊗2RESULTS⊗* 15%  How many values this returns. What domain each is in. Side effects.→⊗8~⊗*
⊗8~⊗*⊗2META-CODE⊗* 70%  The body of the executable code, but with uninstantiated subparts.→⊗8~⊗*
⊗8~⊗*⊗2COMMENTS⊗* 16%  Hints for filling in undefined sections of other BEING parts.→⊗8~⊗*
⊗8~⊗*⊗2STRUCTURE⊗* 4% Viewing this BEING as a data structure, the operations doable to it.→⊗8~⊗*
⊗8~⊗*⊗2AFFECTS⊗* 14%  Other BEINGs which might be called by this BEING, and why.→⊗8~⊗*
⊗8~⊗*⊗2COMPLEXITY⊗* 92%  A vector of utility measures, including probable ease of calling,→⊗8~⊗*
⊗8~⊗*		of success, of (calling)* itself, time/space cost, efficiency of its output results.→⊗8~⊗*
⊗8~⊗*⊗2GENERALIZATIONS⊗* 27%  Some other BEINGs, encompassing this one.→⊗8~⊗*
⊗8~⊗*⊗2ALTERNATIVES⊗* 16%  Some equivalent BEINGs (to try if this one fails).→⊗8~⊗*
⊗8~⊗*⊗2SPECIALIZATIONS⊗* 40%  How to write a streamlined, special-case version of this BEING.→⊗8~⊗*
⊗8~⊗*⊗2ENCODABLE⊗* 9%  How to order the evaluation of the other parts for self-streamlining.→⊗8~⊗*
.SELECT 8
.ONCE TURN OFF "α"
%∞α→$
.TURN OFF "∞→"
.END
.XGENLINES←XGENLINES-3

How widespread was this superfluity mentioned above?
Each of the 100 BEINGs in PUP6 should have
had a value for each part; in reality, only 40% were filled in; only 30% were
actually necessary to generate CF. 

A value for a part is simply a LISP
program which can answer that question, often by asking questions of the
same BEING, of other BEINGs, and of the user. A part may also assert some fact,
create or modify some structure (including demons, BEINGs, and parts of BEINGs).
Appendix 1 shows the values stored under each part
for a typical BEING. 
The reader is invited to glance over this table now.

The set of parts breaks into three rough categories: those parts which
are useful in deciding which BEING gets control, those useful only to
answer the user's questions and keep him oriented, and those used once
the BEING gains control.  Each of these three groups of parts will be
described.

.SSEC(When a BEING Gains Control)

At the humans' meeting, only one expert spoke at a time; in the BEINGs
community, only one BEING has control at any given moment. He uses his
parts to do things (ask, create, modify), and yields control either
voluntarily or through interruption. 

In slightly more procedural terms, the scenario is as follows. One part of
a BEING senses its relevance (often its IDEN or EFFECTS part, each of which is
just a collection of productions. The left side of each production is a template
against which
the current situation is matched, the right side is the corresponding action
to take if the left side matches.)
The IDEN part of BEING B is charged with responding to phrases referrring to 
B, while the EFFECTS part recognizes goals which B might be able to acheive.

If more than
one BEING wants control at any time, a special BEING, CHOOSER, seizes
control momentarily. He asks each competing 
BEING to evaluate its WHEN part, to see
how seriously it needs to go immediately. 
The WHEN part consists of a set of "if <feature> then <weight> because <reason>"
statements. Each <feature> is a predicate to be evaluated on the existing state of
the world; if it holds, then the <weight> program is executed, and returns a
numerical value. The <reason> is an English phrase, unintelligible to PUP6, which
is displayed if the user inquires. 
The numbers are
then simply added to decide how a propos the  BEING  is  at  present.
This  scheme  is  adequate  but  undesirable;  one would like them to
discuss descriptions of what they encounter. In reality, since the  WHEN  part  is
used  only  to  break  ties  between BEINGs vying for control, it
rarely matters what order they go in.  Thus  a  simple,  fast
method  of  selection suffices.

If some BEINGs are still tied for
first place, CHOOSER asks them to evaluate their COMPLEXITY parts, to see which is
the simplest. 
The complexity part is a vector of programs; each is evaluated and returns a number;
the resultant vector of numbers is dot-multiplied into a criterion vector of weights.
This produces a single number for each BEING under consideration.
If any ⊗4still⊗* tie for top, one is randomly chosen. In any
case,the winner is then passed control. 

Once in control, a BEING arranges
some of its parts in some order and evaluates them. For example, the ARGS
part might be first; if it asks for some arguments which no BEING has 
supplied, then the whole BEING might decide to fail. Some  parts, when evaluated,
might create a new BEING, might ask questions which require this whole process
to repeat recursively, etc. 
This "asking" really means broadcasting a request to one or two parts of
every BEING; for example "Is there a known fast way of gronking toves?" would
be asked as a search for a BEING whose COMPLEXITY indicated speed, and whose
EFFECTS part contained a production with a template matching "gronking toves".
A list of the responders would be returned. 
(Incidentally, GERUND would recognize this, but later give up when no one
could recognize "gronk toves".)
The questioner might pose some
new questions directly to these BEINGs, might turn control over to them directly,
etc. One way or another,
the BEING eventually relinquishes control. If it had no direct successor in mind,
all the BEINGs are asked if they want to take over.  
There will always be ⊗4some⊗* BEING who will take over;
the general management
types of BEINGs are always able  -- but reluctant  -- to do so. 
⊗7In fact, at the very beginning, the BEING which first gains control is the
top-level manager: SERVE-THE-USER.
He repeatedly poses the goal "executable
task exists". Various BEINGs respond, including ASK-USER, who has the user
specify what he wants the system to do. After that response is translated,
PUP6 will (hopefully) have some programming task to work on.⊗*

How does each BEING decide which parts to evaluate, and in which order,
once it gains control?
The answer might seem to be difficult or tedious for whoever writes
BEINGs, since it might vary from BEING to BEING. In fact,
it doesn't!
The commitment to a universal set of BEING parts is inefficient in some ways
(each BEING ⊗4needed⊗* only a third of all the parts) but allows for some
simplifications right here. 
What parts should be evaluated, and in what order, when a 
BEING gains control? This decision depends primarily on the ⊗4types⊗* of parts
present in the BEING, not on their ⊗4values⊗*.  But every BEING has the same
anatomy, so one single algorithm can assemble any BEING's parts into an executable
LISP function. Moreover, this assemby can be done when the system is first
loaded (or when a new BEING is first created), and need only be redone for a
BEING when the values of its parts change. Such changes are rare: experts are
not often open-minded. 
The precise algorithm is sketched in the box below. The parts useful here include
ARGS, DEMONS, META-CODE, COMMENTS, ARG-CHECK, and REQUISITES.

.XGENLINES←XGENLINES-1
.BEGIN GROUP
.SPACING 20 MILLS PREFACE 60 MILLS
.TURN ON "→∞"  SELECT 8
.ONCE TURN OFF "α"
⊂∞α→⊃
.SELECT 6
.BEGIN NARROW 3,3 
.ONCE CENTER
⊗2↓_Algorithm for assembling a BEING into an executable function_↓⊗*

When a BEING ⊗4B⊗* first gains control, its ⊗6EXPLICIT-ARGS⊗* are bound. The
⊗6IMPLICIT-ARGS⊗* are initialized, the name ⊗4B⊗* is pushed onto the BEING
control stack, and any newly-activated ⊗6DEMONS⊗* are so tagged. The
BEING who called ⊗4B⊗* should have explained his reasons by assigning
some phrase to the variable ⊗6BECAUSE⊗*.  This reason is now stored as a
special sub-part of the ⊗6WHY⊗* part of ⊗4B⊗*.
⊗6BECAUSE⊗* is rebound periodically in the ⊗6META-CODE⊗* and ⊗6COMMENTS⊗* parts, to
keep current the explanation of each call that ⊗4B⊗* makes. 
Each ⊗6ARG-CHECK⊗* predicate is evaluated. If any returns NIL, the
entire BEING reports that it has failed; otherwise, the
⊗6PRE-REQUISITES⊗* are examined. Effort is expended to make them true, if they
are currently not satisfied. Each ⊗6COMMENT⊗* is evaluated, then the
⊗6CO-REQUISITES, META-CODE⊗*, and the current demons
are executed in pseudo-parallel.  Each ⊗6POST-REQUISITE⊗* is then examined, and
an effort made to satisfy it.  The newly-activated demons are exorcized,
⊗4B⊗* is popped from the BEING control stack,
and the value computed by the ⊗6META-CODE⊗* is passed, 
along with control, to whichever BEING is deemd most relevant.

Some heuristics were devised to take advantage of the fact that the BEINGs often
didn't need many of the standard parts. For example, ⊗6INFO-OBTAINER⊗*
has no new demons or co-requisites, so no parallel processing need be simulated.
No results are explicitly produced, so the value returned by the ⊗6META-CODE⊗* is
not saved and later returned.
Here is the way that BEING actually appeared after assembly;
contrast this with the values of
its parts, as presented in Appendix 1.
Notice that BECAUSE is set to the reason that CHOOSE-FROM is called.
.NOFILL INDENT 4 
.PREFACE 25 MILLS

(INFO-OBTAINER
   (LAMBDA  (U)
        (AND
           (PUSH  INFO-OBTAINER  BEING-STACK)
           (PUT-APPEND  INFO-OBTAINER  WHY  BECAUSE)
	   (EVERY  CURRENT-DEMONS  APPLY*)
	   (SETQQ BECAUSE (WE CAN ONLY TRY TO OBTAIN USABLE INFO IN ONE WAY AT A TIME))
	   (CHOOSE-FROM   
		     (GET-NEW-INFORMATION U)
		     (TRANSLATE U)
		     (ANALYZE-IMPLICATIONS U)
		     (EXTRACT-RELEVANT-SUBSET U))
           (POP   BEING-STACK))))
.FILL
.FPAGE←PAGE
.END
.SELECT 8
.ONCE TURN OFF "α"
%∞α→$
.TURN OFF "∞→"
.END
.XGENLINES←XGENLINES-1

When a BEING relinquishes control, it specifies
which other BEINGs should test to see if they are relevant; typically this set is
either "the BEING who passed me control", "the specific BEING named x", or
"all BEINGs" . The first alternative is hierarchical return, the second is a specific
call by name, and the third corresponds to broadcasting. All the possibly-relevant
BEINGs then run their IDEN and/or EFFECTS productions, and the whole cycle repeats.

.SSEC(Keeping the User Informed)

In the earlier conversation excerpts, the simulated human user had no trouble
whatever understanding what the simulated experts asked him. In the actual
programmed PUP6 system, the human who was sitting at the teletype quite
⊗4rarely⊗* understood what was wanted by the BEINGs. He frequently had to
interrupt them and ask them questions about who was in control, why, what
he was trying to do, what had recently transpired, etc. These ideally can
be phrased as simple retrievals and EVALs of active BEINGs' parts.
The BEING parts
most often called for by the user are the simple one-line "orientation"
templates. These include WHAT, HOW, WHY, and AFFECTS.  For 
theoretical reasons explained
later, the synthesized program, CF, was writen as a pool of BEINGs itself
(by PUP6, but not during the protocol. Actually, a fortuitous 
"bug" in PUP6 created this intriguing situation.)
Although its question-answering ability is inferior to PUP6, the fact that it
has ⊗4any⊗* such power was surprising to the author. In other words,
one can interrupt the target program as it is running
and ask questions. Any BEING on the control stack will provide fully instantiated
answers to any of its 29 allowable queries (its parts); all other BEINGs will provide only
hypothetical answers. As an example, consider this actual excerpt of a human
using the CF program synthesized by PUP6.
(Some liberty has been taken with the
English; e.g., the user really types ⊗4WHAT?⊗*, not ⊗4What are you doing?⊗*)
"???" simply means "guess the name of the scene with these objects and relations".
CF types in ⊗4Italics⊗*, the user in ⊗2Boldface⊗*.

.BEGIN NOFILL FLUSH LEFT SELECT 4

READY TO ACCEPT BRAND NEW SCENE:   ⊗2(??? (A B) (Block A) (Wedge B) (Touches A B))⊗*
NOT AN ARCH. NOT A TOWER. MIGHT BE A ROW.  MY GUESS IS ROW.
WHAT IS IT REALLY?		   ⊗2Nothing⊗*
TRANSFER FROM MAY TO MUST SETS OF ROW: (BLOCK  B)
READY TO ACCEPT BRAND NEW SCENE:
.END

Here is the ⊗2same⊗* excerpt, but with the user interrupting occasionally.
"⊗2U:⊗*"
signifies he has interrupted,
and "⊗2OK.⊗*" signifies he has told CF "⊗2OK, go back to work now.⊗*"

.BEGIN NOFILL FLUSH LEFT SELECT 4

	⊗2U:  What are you doing?⊗*
CF:  Divide a domain into subdomains, using specialized version of PARTITION-DOMAIN.
  	⊗2How?⊗*
CF:  By building up the partition gradually, by adding one <scene, name> pair.    ⊗2OK.⊗*
.D
READY TO ACCEPT BRAND NEW SCENE:   ⊗2(??? (A B) (Block A) (Wedge B) (Touches A B))⊗*
.D
	⊗2U:  What are you doing?⊗*
CF:  Break OBJECTS piece off (??? (A B) (BLOCK A) (WEDGE B) (TOUCHES A B)) to examine.
	⊗2What code is the current BEING going to execute?⊗*
CF:  The meta-code of SOME-PART-OF↓1↓4 is (CADR arg1). Evals to (A B).    ⊗2OK.⊗*
.D
NOT AN ARCH.
	⊗2U:  Why?⊗*
CF: The ARCH MUST-relation (SUPPORTS A B) is contradicted in the SCENE.    ⊗2OK.⊗*
.D
NOT A TOWER. MIGHT BE A ROW.  MY GUESS IS ROW.
WHAT IS IT REALLY?		   ⊗2U:  Why are you asking?⊗*
CF: CF cannot resolve it, and must at this time, so CF asks USER
	⊗2OK. What you wanted is:   Nothing⊗*
.D
	⊗2U:  What are you doing?⊗*
CF: Go through space of concept names, and make user aware of changes.
	⊗2What BEINGs might this affect?⊗*
CF: MESSAGE is possibly called; some version of TEST is possibly called.     ⊗2OK.⊗*
.D
TRANSFER FROM MAY TO MUST SETS OF ROW: (BLOCK  B)
	⊗2U:  Why?⊗*
CF: Change model of ROW until it contradicts the previous SCENE.	   ⊗2OK.⊗*
.D
READY TO ACCEPT BRAND NEW SCENE:
.END

.SSEC(Passing Control in the System)


Rather than delve into detailed discussions about each BEING part which is
useful in passing control, another conversation example will be presented,
annotated as to why each BEING was able to gain control just when it did.
The BEINGs in PUP6 have the same
names, and carry on the same kind of discussion, as our earlier experts do.
Below, they work together to create the idea of structuring CF's internal models'
features into three disjoint sets: MUSTNOT, MUST, and MAY.  After each speaker's
name is, in brackets, a brief sketch of the parts involved in this
particular interaction. These parts are typically IDEN, WHEN, COMPLEXITY,
EFFECTS, and DEMONS. It is advised that the excerpt be read twice: once,
ignoring the information in the brackets, [...], to understand
⊗4what the BEINGs are saying⊗* (how the MUST/MUSTNOT/MAY idea evolves),
and once to attain a feel for how the control-passing parts work.

Assume the "meeting" of BEINGs has progressed to the stage where they know that CF
must compare the inputted scene against internally stored models of named scenes.
When a model is found which passes that comparison, its name is reported as CF's
guess for the scene. A predicate, a test, is desired. The experts ask each other
and the user ⊗4How do we know when a model has passed or failed the test?⊗*

.BBB

INFO-OBTAINER: [⊗7Final course of action in META-CODE part.⊗*] I
am going to consult the user on this matter. Someone take this message, please.

MESSENGER: [⊗7IDEN part recognizes relevance; META-CODE part types on 
teletype.⊗*]  User, how do we know whether the model we're examining is suitable?

USER: Fail if any feature of the model is in contradiction to the
features of the scene.

LOOP: 
[⊗7The IDEN part template "←act if any ←x ε ←X satisfies P(x)"
matches the last sentence. "act" is bound to "fail", "x" to "feature", etc.⊗*]
The outer structure called for is a loop through the model's features,
terminated when some test fails.

CONTRADICTION: 
[⊗7The IDEN part can handle "←x is in contradiction to the set ←Y"⊗*.]
This failure should occur
precisely when the model demands some property of a scene feature which that feature
doesn't possess. 

SCENE: 
[⊗7The IDEN part prods the STRUCTURE part, which already
understands what a scene is composed of, in particular what constraints are
imposed on the features.⊗*]
The only properties the scene's features can possess are that of absence and
presence. The user has already ruled out negation and combination of features.

TRANSLATE: 
[⊗7EFFECTS include uniting two related sentences, using substitution.⊗*]
Thus the predicate should return failure if the model specifies that a
feature be present and it is actually absent, or if the model specifies a feature
be absent when it is actually present in the scene.

PGMMER: [⊗7WHEN part has a very high rating now.⊗*]
I believe that, with LOOP's help, we understand this enough to program it.

CODER: 
[⊗7EFFECTS indicate this is the only BEING who should be active now.⊗*]
Give me the arguments and the body of the code.

LOOP: 
[⊗7DEMON recently set up just for this occasion is triggered.
SPECIALIZATIONS part now produces streamlined version of LOOP BEING itself.⊗*]
The arguments are two pointers: to the features of a model and to the
features of a scene.
The outer structure is to step through the model features until the test
returns failure. If this never happens, then report success.

PGMMER: 
[⊗7DEMON triggered here also. COMMENTS part contributes knowledge of
how to handle cases at this level.⊗*]
The testing function must check each model feature. If it is one which
must be present in the observed scene, then check for that presence. If it is one
which must be absent, check that it is in fact absent.

CODER: 
[⊗7Summoned by its EFFECTS part. META-CODE part suggests using COND for cases.
COMMENTS part warns that this only works if case tests are disjoint.⊗*]
I want to embed the tests in a COND. Can a model feature demand itself be
both present and absent from a scene?

SCENE: 
[⊗7IDEN grabs this. STRUCTURE part indicates that they are disjoint.⊗*]
No.

CODER: (scribbling)
.BEGIN NOFILL GROUP SELECT 6 INDENT 0
 (LAMBDA   (M-FEATURES  S-FEATURES)
   (FOR-EVERY  M-FEATURE  IN  M-FEATURES  
     (COND
       ((IS-OF-TYPE  M-FEATURE  MUST-BE-PRESENT)   (MEMBER  M-FEATURE  S-FEATURES))
       ((IS-OF-TYPE  M-FEATURE  MUST-BE-ABSENT)    (NOT (MEMBER  M-FEATURE  S-FEATURES)))
       (T     ...))))
.END
What happens if the model feature doesn't have to be present ⊗4or⊗* absent 
in the scene?

.INDENT 2

CONTRADICTION: 
[⊗7IDEN part recognizes relevance, WHAT part easily answers the question.⊗*]
Then there can be no contradiction. (Blank stare from CODER.)

PGMMER: 
[⊗7IDEN part is not anxious, but CODER's is even lower-valued. Examines the
CODE part of the TRANSLATE BEING.⊗*]
He means, the test function should return T.

.INDENT 0

CODER: 
[⊗7Regains control hierarchically. A REQUISITE must now be satisfied.⊗*]
Got it...  
This is still very tentative; does anyone see any undesired properties
of this piece of code?

CASE-SPLIT: 
[⊗7IDEN part responds, WHEN part is high enough to take control.⊗*]
That call on IS-OF-TYPE is too general, would take too much time. I
know a great deal about case testing. Explain to me what exactly is needed, and I
will replace each IS-OF-TYPE call by a much more efficient one.


.ONCE INDENT 2
GENL-MANAGER:
[⊗7IDEN reluctant; must fall back on very general management techniques.⊗*]
No one seems to understand you. Go through your bag of "tricks" one by
one, in detail.

CASE-SPLIT: 
[⊗7WHAT and HOW parts are presented to the pool; hoping for recognition.⊗*]
Many of the 
tricks deal with changing the internal representation of sets, to
make searches on them more efficient. Is their any constraint on how the features of
a model be stored?
(pause) Well, the biggest savings would result from replacing IS-OF-TYPE by the
fast function MEMBER. The next biggest gain would be to store all the "must be 
present" features before all the...

STRUCTURE-INDUCER: 
[⊗7IDEN indicates very high relevance. META-CODE is able to handle one of the
"tricks" all by itself.⊗*]
Wait. I don't see anything wrong with your first idea.
The model's features will be divided into 4 disjoint sets: those which must be
present, those which must be absent, those in both, and those in neither class.

SCENE: 
[⊗7DEMON part says that an inefficiency was just overlooked; COMPLEXITY
says it is urgent.⊗*]
There can be no features which must be both present and absent.

STRUCTURE-INDUCER: 
[⊗7Continues on⊗*]
So CF maintains 3 differently-named sets of features
for each model.

PGM-MANAGER: 
[⊗7COMPLEXITY has just risen past danger level.⊗*]
This seems like too big a step to go unreported to the user.

MESSENGER: 
[⊗7EFFECTS indicate this is the only BEING to call on now.⊗*]
I will tell him what was done. If he asks any questions, I'll relay
them back to you.

PGM-MANAGER: 
[⊗7REQUISITE part warns that this must be done soon.⊗*]
We must have proper names for the three types of sets.

NAMER: 
[⊗7EFFECTS part shows this is the ideal BEING to take over now. CODE does the
simple initials/mainwords/concat operations to produce mnemonic labels.⊗*]
How about "PRESENT, ABSENT, EITHER"?

USER: No. Call them "MUST-BE-PRESENT, MUSTNOT-BE-PRESENT, MAY-BE-PRESENT".

NAMER: [⊗7Length DEMON awakens⊗*.] 
Too long. We shall call them just "MUST, MUSTNOT, MAY".

WARNER: 
[⊗7WHEN sees relevance, META-CODE says to locate areas which will
possibly need revision.⊗*]
All previous accesses to models' features have been located and tagged.
Now what?

STRUCTURE-INDUCER:
[⊗7Specialized facts about the effect of substitutions on earlier code.⊗*]
Each such access must either be replaced by APPEND of three accesses, to
the three new names for sets of model features, 
or else the statement it is in must be replaced
by three similar statements.

ANALYST: 
[⊗7DEMON part wakes up at this blunder.⊗*]
Not always: not all three types of features may need
to be accessed each time.
.END

Considering the thousands of inter-expert transfers which preceded completion of
CF, it is not surprising that all these brief excerpts seem somewhat defocussed.
This price is tolerable since the BEING execution times are small, and since
the uniform structuring (which causes this lack of direction) benefits more than
it hurts (the system actually ⊗4works⊗*).

.NSEC(Theory of Pure BEINGs Systems)

We now discuss the constraints each BEING, and each group of BEINGs, must
conform to. Hopefully, ideas will be separated from implementation
details, prejudices from  plausible features.

It would be aesthetically pleasing to restrict all entities in the system to be
BEINGs. However, this would cause an infinite regress, 
as each part of each BEING would
have parts which had parts... To stop this, one can assert that at some finite
level, all constructs are primitive. ACTORs, for example, set this level to
zero; BEINGs set it to one. ACTORs themselves are primitive, 
but only ⊗4parts⊗* of BEINGs can be. For this reason, BEINGs can not be
viewed as a convergent recursive definition, while ACTORs can be.

Suppose it were decreed that the only autonomous entities possessing control
abilities were BEINGs. 
In particular, we forbid any plain ⊗4functions⊗* to
exist.
In the case of an automatic programming task, the BEINGs would have to write new
BEINGs, not new LISP functions. The target program would thus itself be a
community of BEINGs. 
In order to fill in all the parts of the synthesized BEINGs, a vast amount 
of superfluous information would be collected. These supplementary
facts can be viewed as a standardized, organized body of
⊗4documentation⊗*, a formatted system of comments tacked onto each BEING produced.

Which BEINGs would write the new BEINGs?  Looking back at our interdisciplinary
experts, we see that each expert is responsible for distilling his own essential
contribution, which is then encoded by a programmer.  Perhaps each BEING should be
able to direct construction of new, specialized BEINGs which relate to it. If
no BEING relates to a task, then it can't be coded; if several respond, they
should cooperate. This ability is in reality the SPECIALIZATIONS part of each BEING
(see box, Section 7). The BEING which actually does the creation
(⊗6CODER⊗*) in the experimental system is almost trivial, getting very
precise instructions from other BEINGs.

Since the pool must communicate with the user, some BEINGs must translate
quasi-English phrases into calls on BEINGs.  Drawing again on our experts
analogy, we require that each BEING recognize his own relevance. So translation
is merely the act of asking the whole pool "Who can recognize this...", collecting
the responders, having ⊗4them⊗* decide who should take control, and letting the
winner do the translation. Most communication is done as if it, too, were such
a translation activity.

One bias is the rejection of debugging as a fundamental programming tool.
It is felt to be worth the extra effort to make the system's internal model of the
current partial target program ⊗4correct⊗*. Debugging demands detective work,
examing one's earlier efforts for flaws, for details which have been overlooked.
Any tireless system  should not
ignore details, but rather defer them,
asserting a warning to this effect when it does so. 

Another unjustifiable tenet of PUP6 is that procrastination 
is quite valuable; PUP6 always expends much effort
deferring any unresolvable decision.
Undeferrable unresolvable decisions must cause a backtrack  point to be
reluctantly set up. 

A third prejudice is that most carelessness bugs can be 
eliminated by this deferral, feed-forward, and precise record-keeping. Humans
depend on their adaptability to compensate for limitations in their brain
hardware, but there is no need for an ⊗4automatic⊗* programming system to do so.
These biasses are not inherent in the BEINGs formulation, but only in the design
of the PUP6 system (and in the mind of the author).

To clarify what BEINGs are and are not, they are contrasted with some other
ideas. FRAMES[MIT2] are sufficiently amorphous to subsume BEINGs. In philosophy,
FRAMES are meant to model perception, and intentionally rely on implicit
default values; BEINGs intentionally avoid making decisions by default.
As  an
example,   consider   the   writing   of  a  short,  recursive,  list
manipulation LISP program (reverse, flatten, assoc, alternate,  etc.)
A human, consulting the proper frame in his head, knows to ignore the
base step for a while, then fill it in, usually  as  ⊗4if  NIL,  then
NIL⊗*.  The
human makes this default synthesis, tries out the program, and  looks
closer  (to fill in this "slot" properly) only if something calls his
attention to it (such as a LISP error message:
NON-NUMERIC ARG  ⊗4NIL⊗*, e.g., if what was really needed was the base
step ⊗4if NIL, then 0⊗*).
A BEINGs system would
also  defer working on the base step, but could -- and would -- place
a note about that deferral into the assertional warning base.  Before
thinking  it  was  finished,  the  system  would  attend to that note
carefully. This is not a criticism of FRAMES:   
as a
construct  to  model  perception, the default concept
makes sense for them. BEINGs are clearly non-anthropomorphic in their
internal  workings,  and  would  be very awkward models of human
perceptual mechanisms.
	HACKER [MIT2] differs from PUP6 in the same  qualitative
way as FRAMES do from BEINGs.
The orientation of HACKER is to put together pieces of programs
into something close to the final desired target, then  try  and  run
it.  When  errors result, they are analyzed and then patched.  PUP6
is oriented toward writing bug-free code; what it writes must  always
coincide  with its internal specifications of that code. The user may
later change his mind, and the  system should be (and occasionally is) 
able to modify its
own  programs,  but  this  process  is much better defined than blind
debugging. On the other  hand,  if a BEING in PUP6 does  have  an
unexpected bug in it, the system may not be able to recover from it. One
way to overcome this would be to include special recover-from-bugs
BEINGs.
	The  formal  manipulation  systems which also synthesize code
are so different from PUP6, that it is difficult to  compare  them.
These  logical systems (e.g., [Luckham]) attack an entirely different
problem.  Their task is specified rigorously  in  advance,  and  they
proceed  formally  to  search  for  a  solution  program.  BEINGs are
designed to work on a much higher level, heuristically.  Each  action
is  implicitly justified by the fact that the user can later describe
to the system
what is undesirable about the program it's generated. That is, PUP6
may tolerate some  user ambiguity and error, at the expense of later having
to modify what it has written.
	Like  ⊗4any⊗* Automatic Programming system which 
writes structured programs, the
external behavior  of  PUP6 must be
reminiscent  of  macro  expansion regardless of ⊗4what⊗* the internal
BEING  interactions  are.  One  major  distinction  between  the  two
concepts is when and how the macros are expanded. Traditional answers
are:  at  compile  time,  by  rigid   substitutions.
BEINGs  systems expand their "macros" at
times they choose, using knowledge gleaned from each other  and  from
the  user.
Macro procedures expand mechanically:
⊗2expand(sequence   m↓1  m↓2) = (sequence  
expand(m↓1)  expand(m↓2)))⊗*. BEINGs could use
information gleaned during expansion of m↓1 to improve the way m↓2 was handled.

ACTORs[Hewitt], unlike BEINGs, have no fixed structure imposed, and do not broadcast
their messages (they  specify who gets each message, by name, to a bureaucracy).

The theoretical danger of BEINGs is that no small universal parts may be found; in
fact, this is why we specified our task (writing inductive inference LISP programs)
before deciding upon a set of BEING parts. Even so, each part was really only needed
by about one third of all the BEINGs in the system.

BEINGs subsume (inefficiently) many popular AI features;
the demonstration will be brief:
A ⊗4demon⊗* could be replaced by a BEING whose ARG-CHECK predicate was the
triggering predicate, whose WHEN part was high enough to ensure frequent
attention, and whose META-CODE part was the body of the demon. An ⊗4assertion⊗*
in an associative data network
could be a BEING with only an IDEN part filled in; when it recognizes its
relevance, a fully instantiated assertion is returned. A ⊗4function⊗* is
equivalent to a BEING with only a META-CODE, ARGS, and EVAL-ARGS parts; one knows
almost nothing about it before executing it.
The inefficiencies should be clear: whenever a BEING throws a question open to the
floor, "Who can...", it takes an amount of time proportional to the number of
BEINGs in the system. One would introduce this huge time factor by 
replacing any of the above mechanisms by BEINGs.

The ⊗4number⊗* of BEING parts  seems to indicate 
the balance between uniformity and structure in the community.
This was touched on as point (2) of Section 6.
A small universal set of BEING parts is necessary to
preserve some of the advantages of uniformity
(easy addition of knowledge to the system, easy inter-BEING communication). This
demands that the number of parts of each BEING be, say, under 100. But it is
the complex structure of a BEING which makes complex behaviors feasable, including
flexible communication as well as viable final products. 
So each BEING should have many parts, say at least ten.
This range, 10 to 100, is wide for the domain of automatic programming. In other
domains, it may be narrow or disappear altogether; this would indicate that
BEINGs could ⊗4not⊗* be used effectively for those tasks.

.MIXPAGE←PAGE
Another way to view this is to examine the two possible extremes:
If each BEING may have only one part, then that part must answer
one universal question which
encompasses everything; this question must be of the form "tell me everything you
know," and means that we have a completely uniform formalism. At the other extreme,
each BEING has a separate part for each conceivable type of question it can answer;
all the uniformity has disappeared. 
.NSEC(Experimental Results)

	The nature of the task is of course central to any discussion of
performance.  For that reason, this section will deal more with automatic
programming than with representing knowledge.  The success of an AI effort
can be assessed only where accepted standards of intelligence exist.
The  character of the dialogue seems to be the clearest external
measure of the  intelligence
of  an  AP (automatic programming) system.  
One which asked "What is the first instruction?
What is the second...?" would be universal but worse than useless.
Equal in importance to dialogue
flavor is the final product of the system: what programs were actually
synthesized?  PUP6's answers to these two questions are the first two subsections
below. Finally, we treat some less central questions.

.SSEC(Character of the Dialogue between User and PUP6)

By lumping all the parts of the PUP6 system together conceptually, the
interaction is seen as a ⊗4dialogue⊗* between a human user and an automatic
programming system.  The level of detail maintained in the earlier polylogues
obscured what the human actually saw and responded. Below are those same excerpts,
but as the ⊗4user⊗* would see them.

Here are the initial few lines of an actual 300-page long dialogue. In section 4,
this excerpt was presented the way experts (and the same way the PUP6 BEINGs)
discussed it.
.BEGIN NOFILL

PUP: I want any task.
USER: Write a program which does concept formation
PUP: I am about to write a program for ⊗6specialized CONCEPT-FORMATION⊗*. 
PUP: Give me a proper name for this program. (I suggest CF or CONCEPT)
USER: CF
PUP: Must CF mimic different human subjects? (respond YES, NO, ?, or DETAILS)
USER: NO
PUP: I am temporarily replacing the task "⊗6specialized form of CONCEPT-FORMATION⊗*"
  		by "⊗6specialized form of PARTITION-A-DOMAIN⊗*".
.END
From the above, one gets the true impression that the dialogue was fairly tedious:
choosing names and resolving design decisions ⊗4was⊗* 
the user's main role. There were,
in sum, about 300 such responses involved in generating CF. 13 crucial responses
were also necessary,
where the user supplies needed information that was not explicitly requested by
the BEINGs.
A few of these key lines are: Write a program which does
concept formation; an "element of the domain of stimuli" is a static scene; the
guessing process is one of searching, not computing; terminate the loop iff any
model feature is incompatible with the scene's features. In addition, the user
must check over each decision to transfer between the seven current sets of
features (MAY/MUST/MUSTNOT of the guessed and the correct model name; SCENE 
features): what gets transferred, when, and why. {There ought to be ANALOGY BEINGs
which learn from the first couple such tedious constructions, and answer for
the user during the writing of the last several transfer functions.}

The translation mechanism is simply the IDEN parts of all the BEINGs. Each such
part contains a few productions, which are united with those of the other BEINGs
into one large production system. The left side of a production is a template
which is matched against the given phrase. The right side is a small program to
be executed in case the phrase is recognized. Generally, that program simply says
to translate some subphrase of the phrase, and then (probably) pass control
to the BEING which this is in the IDEN part of.
While not up to the "state of the art" in natural language processing, this is both
adequate and faithful to the spirit of distributing problems over 
all the BEINGs, by making them ⊗4parts⊗*, so it is each BEING's duty to know a
little about them.

In the excerpt presented in
section 7.4, again only the first user comment is other than a simple choice.
Consider that excerpt from the point of view of the
user:
.DPAGE←PAGE
.BEGIN NOFILL INDENT 4

PUP: Please type in a logical expression which is true iff we terminate the loop
USER: Any feature in model-features is incompatible with scene-features
PUP: PUP wants USER to type in name for specialized version of CONTRADICTS
USER: Call it IMPOSS
PUP: Move cursor to IMPOSS type of CONTRADICTS. I can no longer defer this decision: 
.GROUP
    	   A... Contradiction arises from features who have probability=1 of occurring
	   B... Contradiction arises from features who have probability=0 of occurring
	   C... Contradiction arises from features who have probability>0&<1 of occurring
.APART
	Please type some sequence of some of the letters A,B,C; or type ?, DEFER, or DETAILS.
USER: A, B, and C are all relevant.
PUP: I recommend that each model's features be structured (along 1 dimension) into these 3 pieces:
.GROUP
	PRESENT, which will hold features whose occurrence should have probability=1
	ABSENT,  which will hold features whose occurrence should have probability=0
	EITHER,  which will hold features whose occurrence should have any other probability
.APART
     Please type back YES, NO, UNSURE, DETAILS, or 3 new names.
USER: YES. Call them MUST-BE-PRESENT, MUSTNOT-BE-PRESENT, MAY-BE-PRESENT.
PUP: Too long. Nicknamed MUST, MUSTNOT, MAY.
PUP: In all code generated to date, three references to model's features have been located.
PUP: In all cases, reference has been replaced by (APPEND MUST MUSTNOT MAY).
.END

Because of its genesis from a single "experts meeting" polylogue, hereafter
referred to as the ⊗4protocol⊗*,
the pool of BEINGs was simply
not capable of widely varied dialogues with the user.  
Two assumptions implicit 
in using the simulated experts' discussion as a literal model
turned out to be serious: the abilities of any
actual user of PUP6 must coincide with those of the user who was simulated in the
protocol, and the order of and wording of the actual user's comments must closely
adhere those of the user in the protocol. Such difficulties must be overcome
in any system
designed for wide usership, but were considered ignorable in the specific
automatic code generation task at hand.
In fact, "the user" is not used generically; there was, alas, only one successful
user.

Also
as a result of this approach to system specification, each BEING had only those
parts specified which it actually would need in the ensuing dialogue.
Part of the difficulty with new dialogues stemmed from this minimal completion.
In the protocol, when a decision was made by experts,
the knowledge necessary to follow the
⊗4other⊗* alternative branch was not used, nor were such superfluous
facts supplied to the BEINGs in PUP6. Thus
the user of PUP6 must almost always resolve each choice the way the simulated
(protocol) user did.
It is felt that if all the parts of all the BEINGs had been faithfully filled
in, this problem would have subsided. Basically, the difficulty is one of
modelling all the possibly relevant knowledge an expert has, rather than
(as was done) just capturing enough of his knowledge to do a few given tasks.

While all the BEINGs' interactions were invisible to the user, the system still
swamped him with data about what was going on. For example,
most of the entities he was asked to name were never referred to again by name. The 
converse problem existed as well: it was necessary to include a BEING which
simulated forgetfulness, to prevent, e.g., anaphora spanning minutes of real time.
Orienting the user was not solved satisfactorally. Pointers into
a graph of generated code were simulated, but often a user wished to refer to
a piece of code not by name or by pointing, but by some brief meaningful
(to him only!) phrase.

.SSEC(The Range of Programs Synthesized by PUP6)

The system, PUP6, did eventually synthesize CF, 
the target concept formation program.
PUP6 was 200 pages of INTERLISP[Teitelman],  CF was 30 pages long (6 pages when
coded by hand during the protocol). This was generated in 60 cpu minutes
(compiled, PDP-10 TENEX). The dialogue consisted of 300K characters typed by
PUP6, and 4K by the user. It occupied 300 pages, and five hours of real time.

Despite the lack of dialogue flexibility,
it ⊗4was⊗* felt that
most of the BEINGs could be useful in generating other programs. For this
reason, two additional target programs were specified. They were 
synthesized with little change to PUP6, but only by someone familiar
with the system.

The second target program, GI, is a grammatical inference program, which accepts
strings labelled LEGAL, ILLEGAL, or ??. In the latter case, GI must guess the
legality. Internally, sets of plausible rules are built up.
It doesn't enumerate  through  the space of all grammars, at least, but it
lacks most of the "tricks" of  the  best  g.i.  programs.
In some versions of GI the user coaxes
PUP6 to generate, a parse tree may be maintained  and  inspected;  in
other versions, just a list of the rules used during a parse is kept.

Of the original
pool, 46 out of 70 "general" BEINGs were used in synthesizing both targets.
Three of the existing 17 
"domain-specific" BEINGs also were useful (those involving partitioning).
Four totally new BEINGs had to be added, related to formal grammars and rules.
Unfortunately, the addition of ⊗4any⊗* new BEINGs demands that the
user be acquainted with the format conventions of PUP6.
The GI program generated was 20 pages long; a hand-coded
version was one-fifth that size.

PL was the final target program attempted, a simple property list manipulator.
The user repeatedly types
in a request to insert, delete, or inspect a  record  (e.g.,  INSERT:
PASSENGER  Jones  FLIGHT  741  FROM SFO TO LAX CARRIER TWA LEAVE 7:15
ARRIVE 8:00).  Any unspecified fields are treated  as  don't  cares;
the request is matched against entries in the data base,
so a simple
pattern-matcher had to be synthesized.

39 ⊗4general⊗* BEINGs were used in synthesizing ⊗4all three⊗* targets, but no
⊗4domain-specific⊗* BEINGs were common to synthesizing PL and any other program.
One general BEING and one domain-specific BEING had to be ⊗4added⊗* to PUP6.
	The table below shows how each type of knowledge was used  in
writing the three target programs.  All numbers refer to BEINGs.

.BEGIN
.GROUP
.NOFILL
.SELECT 9
.INDENT 4
.BREAK

.ONCE CENTER
        ⊗5U  S  E  D     I  N     S  Y  N  T  H  E  S  I  Z  I  N  G⊗*         

TYPE OF          CF    CF    CF    CF     GI    PL     not     Crea    Crea    Crea    Total 	 Total
KNOWLEDGE        GI    GI    PL  only   only   only    used    -ted    -ted    -ted    BEINGs	 BEINGs
                 PL  only   only                       ever    in CF   in GI   in PL		 in PUP6

Programming      39     7     5     5     3      1       14       52      27      21      174	    74
Domain-Specific   0     3     0     9     8      1        5        4      10       3       43	    26
Total BEINGs     39    10     5    14    11      2       19       56      37      24      217	   100
.END

The first seven columns refer to BEINGs initially in PUP6. 
In the next three columns,
"Created" means "written by PUP6 during the dialogue which synthesized".
Notice the encouraging percentage of programming BEINGs  which  were used in  all
three dialogues (39/74). The three domain-specific BEINGs used
in both CF and GI  sessions  indicate  that  they  may  be  Inductive
Inference  domain specific.  They aren't used in  PL, which is not an
inductive inference task. All three deal with partitioning a domain.
A  specialization of a general programming BEING is listed as
a programming BEING still  (in  the  CREATED  columns  of  the  above
table.)  This  is  because  it remains sufficiently independent to be
used in many ways, conceivably in many different programs.

As proposed in Section 8, the BEINGs generate other BEINGs, never plain
functions. This explains the huge increases in target code lengths
in the PUP6 versions compared to the versions produced by hand when
simulating the experts (who wrote the target programs as functions).
CF was a pool of 56 brand new BEINGs, GI 37, and PL 24. As
with PUP6, one can interrupt the target programs as they are running
and ask questions. Any BEING on the control stack will provide fully instantiated
answers to any of its 29 allowable queries (its parts); all other BEINGs will provide only
hypothetical answers. Recall the excerpt from CF itself running, found in section
7.3.
	The  style  of  the synthesized programs is constrained since
all code must be BEINGs. At a lower level,  there  are  many  trivial
inefficiencies which are passed through a BEING which is to optimize
LISP programs out of context, at a low level.  This BEING is
vacuous now, but may soon contain a LISP optimizer being  written  by
A.  Cohn of the SAIL AP group. Low level efficiency was intentionally
ignored to expedite work  on  PUP6.   Nevertheless,  the  final  code
produced  runs  in  about  the  same  time as the hand-coded versions
(e.g., a few seconds per scene for CF).  It is several times as long,
though,  since  it  must  be able to answer questions about what it's
doing as it runs. The program produced by the system-player during
the original protocol  lacked  this  ability,  of
course.
	Although BEINGs can theoretically handle
user errors, PUP6 was set up expecting that the user would never  err
or  forget.  He could, after the program was finished, try it out and
describe how he wished it changed. Occasionally, PUP6  actually  made
the  right modifications. For example,  PL,
the simple data storage and retrieval on keys
system which was written, was supposed to accept, access, and eliminate
reservations.   After the synthesis is finished, the user tries
out the program and finds that he is unable to delete more  than  one
reservation  with  any  single  command. He complains about this, and
PUP6 modifies the program so that he may specify a pattern,  and  all
reservations  matching  that  pattern  will  be  purged.   

The sentence the user must type in to get PUP6 to make this change is
twenty words long, very stilted, and almost unique. Any deviation would cause
it to fail to be recognized by PUP6. This demand on the user is actually
far more pervasive and far more serious.
While assumptions of absolute 
user reliability are reasonable for  little  programs,
they  break  down  when the tasks reach the size of tens of pages and
hours.

Some of the difficulties stem from the nature of the task. In any long dialogue,
the user often forgets, changes his mind, errs, etc. A very sophisticated user
model would be necessary to accomodate this errorful process in a
non-debugging system. 
Without such abilities, the system itself may be led into error.
While most bugs ⊗4are⊗* avoidable by careful
record-keeping, it proved unrealistic to make no provision for debugging a
new thirty-page program. When a few errors did occur, PUP6 itself had
to be altered.  

.SSEC(Questions for Automatic Programming Systems)

We now list some features one should inquire about when
confronted by any new AP system 
which generates code heuristically from a dialogue.
The questions break into
three categories: what it produces, 
the theory behind it, and the way it actually works.
Capsule answers pertaining to PUP6 are parenthesized after each question.

 	⊗2↓_Category 1: What it Produces_↓⊗*

	Of all the things it does, the first one to inquire about is
"does it write a program?"
(yes.)
If  so,  how  complex  is  that  task,  and  what  is   the   program
specification  like? (a concept formation program, several pages long,
from one specific protocol dialogue).  
How precise must the user be:    may he err (no),
forget (no), change his mind? (only in limited cases.) 
How detailed must his  dialogue  be? (by construction from the protocol,
just about as
detailed as if he were talking to a CS grad student programmer.) How
closely  does  the  dialogue determine the details of the final code?
(some inferences are made, and several representational choices, but
much of the 
final code is clearly determined by the precise user responses.)
How does the user know where he is during the dialogue? (simulated cursors
pointing to a graph representing synthesized code.)
Does the user ever get lost? (often.)
	Quite  seriously, an important question is whether the system
writes a second program. (yes.)  
If so, how does it relate to the first  one
synthesized? (both are inductive inference LISP programs.) 
How much of the AP system is actually used in writing
⊗4both⊗* programs? (49 BEINGs out of 79.) 
One should ask what the full range of programs is
which  the system has successfully synthesized. (the concept former CF, the
grammatical inferrer GI, and the simple information manipulation system PL.)
The dual questions to
these inquire whether a program may be generated by several different
[in the sense of rephrasing and in the sense of reordering the subtasks]
dialogues (theoretically, but not practically),  
and  what  the  range  of variability is. (theoretically large, but
practically quite limited.) Similarly, what
about the target language: is it a parameter? (no, always the same.) 
How does it  relate  to
the language the system is written in? (both written as BEINGs in 
INTERLISP.)
	Does the system modify as well as write code? (yes, but not
as its major mechanism.)   If so,  can
it  modify  anybody's,  or only those programs it has written itself?
(only its own, and only in a few very simple ways.)
What is its "style" of programming? (many supplementary comments,
fairly clean structured programs only.) 
One also wishes to know the  size
of  the tool as well as the size of the job: How does the system size
compare to target program size? (one order of magnitude larger.)
	Efficiency considerations are often the crucial
pragmatic ones. Economics and current hardware restrict the amount of
computation  which  may be done in toto; the expected lifetime of the
universe restricts us from using the  most "elegant" algorithms;  and
human  patience  restricts the interaction delay time (to a minute or
two of real time). One must therefore  ask  things  like
how  much  time  and  space  it  requires,  how long a delay there is
between user inputs, etc. (one CPU hour, 100K, under a CPU minute 
between responses.)

 	⊗2↓_Category 2: The Theory Behind It_↓⊗*

	The  second  class of questions concerns the theoretical side
of the AP system.  What new ideas is it meant to experiment with? 
(using BEINGs to write large programs).
What is wrong with the ideas? (All the nonuniformity is simply pushed down into
the contents of the BEINGs' parts; not all parts will be meaningful to all BEINGs.)
What is good about them? (Compromise between structured and uniform representations
of knowledge; supportive analogy from human experts.)
How do these ideas fare in practice? (mixed, but promising; this is the subject
of most of the remainder of this paper)
	Does the system write its code in the "right" way, 
does it follow a reasonable course of
action to do the synthesis?
(PUP6 asks the right questions of  the  user  at  just  the  proper
times with respect to the original protocol. This was built in as one of its
design constraints).
How extendable is the system: how difficult is it to add new pieces
of knowledge and to modify old ones? (theoretically easy, practically it
requires familiarity with the system.)  Could  it  write  programs  in
various fields (possibly), in various styles (unlikely), in various sizes?
(perhaps, but the three target programs 
actually synthesized differ by less than one order of magnitude.)
	How is knowledge  represented  internally? (BEINGs, assertions,
demons.)   Is  any  of  it
duplicated? (not much above the LISP language level; some universal
knowledge is factored out; e.g., how to CHOOSE-FROM a set of BEINGs.)
If so, why is it duplicated? (becaue some of it is too primitive to factor out
into higher-level BEINGs; e.g.,
how to bind variables.)  

 	⊗2↓_Category 3: How it Really Does It_↓⊗*

The third type of question is "what is the internal mechanism of the synthesis?"
That is, how does it really write new lines of code?  In the case of PUP6, the
prime mechanism is the ⊗4creation of new, specialized BEINGs⊗*. That is, one or two
BEINGs get together, figure out what has to be done, introspect enough to see how
they are able to do the task, then extract bits and pieces of themselves, specialize
them to the task at hand, and make them into a new BEING. Other BEINGs then sense that the
new one is incomplete, and work to fill him in more, to smooth him into the system.

Two mechanisms which PUP6 relies heavily upon deserve illustration. They are
demons and comments.   The DEMONS part of INFO-OBTAINER says to activate the
demon alled Fringe_of_Consciousness.
This name was chosen because its function is similar to the "impossibility"
mentioned in [Dreyfus].   In  the  course  of
writing  GI,  the  system  learns  that  the  main  task  is  one  of
grammatical inference.  The GRAMMAR BEING then  asserts
that  if  the  user ever mentions the word ⊗4TEST⊗*, he may actually mean
⊗4PARSE⊗*.   This assertion is placed in the IDEN part of the TEST  BEING,  and  is
therefore   only  demonized,  waiting  on  the  periphery  of  PUP6's
concentration.   It is in fact triggered later in the dialogue, as an
inference surprising to the user.

	Active use of comments proved helpful. 
Some assertions are so meaningful  to  the  user,
that they are stored in the code itself, even if they are
only temporary.  At any time, the user
may look at a piece of code; the comments present  ⊗4then⊗* are  all
assertions pertaining to that piece of code at that time.
BEINGS may use comments at  several  different  levels.  At  the
lowest  level,  each  comment  is  merely  a  unique token; it may be
inserted, removed, or searched  for.   Slightly  better,  the  BEINGs
system can ask "is there a comment involving ...". For this purpose, a
constrained syntax for the comments should be developed. Otherwise
(as, unfortunately in PUP6) each new comment must be attended to
ad hoc. As an example, the
comment at the end of the main outer loop was "COMMENT, INFINITE LOOP
IN THIS PROG" (see Appendix 5) for most of the session. Near the  end
of  the  session,  the  CLARIFY_IMPROBABLE_SITUATION BEING recognizes
this as a warning, works on introducing a breakaway  test,  and  then
replaces  the  comment by one indicating that no infinite loop exists
there anymore (see  Appendix 4).   The  advantage  to  embedding  our
insertions in the code this way is that, at any stage, the user can
inspect the code and get something meaningful  out  of  the  comments
which are present.

	Some of the BEING parts  proved  embarrassingly  unnecessary.
The  CO-REQUISITES  part was never used.  The only activity which had
to be done concurrently was demon activation. The AFFECTS part was of
interest  to  the  user  occasionally,  but  never to any BEING.  The
EFFECTS part originally had a twin, describing what would  happen  if
each  BEING  were  ⊗4not⊗*  called right now.  In each case, this was
merely a trivial restatement of the frame problem.  So,  like  STRIPS
[Fikes],  PUP6  ignores  the  frame  problem:     all changes must be
explicit.

.NSEC(Conclusions)

.ONCE FLUSH LEFT
.SSEC(About PUP6)

What have we learned from this experimental study? The overall
feasability of BEINGs was demonstrated, but the difficulties of communicating
with the user made the system almost impossible to work with. 
The set of
questions the user was expected to want to ask is the same as the set that one
BEING can ask another: the BEING parts. When the "nice" user interrupts, his
questions are translated trivially into a simple retrieval. Real users are
seldom nice; the BEINGs generally misunderstood what users asked.
	First  the bright side. The increment to PUP6 to enable it to
write the GI and the  PL programs is encouragingly small. Almost  all
the  programming-knowledge BEINGs are called in writing more than one
of the programs. It is now clear  that  very  domain-specific  BEINGs
were in control at the early, high levels. Later, more general BEINGs
took over, followed by pure programming BEINGs.  The middle  category
would  include inductive-inference-specific 
BEINGs like PARTITION_A_DOMAIN.  
	Regrettably, incrementing the system with new domain-specific
BEINGs is not feasable for the average user.  To add a BEING, he must
specify  all  of  its relevant parts. Each is inputted either as LISP
code, as an English sentence PUP6  is  capable  of  interpreting,  an
English  sentence  PUP6  is  just  supposed  to  remember as a canned
response, or by pointing to a part of an existing  BEING  and  saying
"like  that  one,  except  ...", where the  ellipsis must be
very simple.  The interactions between the BEINGs, and  the  existing
set of BEINGs, need not be fully understood; but the set of allowable
assertion templates, the mechanisms by which each part is  used,  the
special  data types involved (VECTOR, TUPLE), and the precise actions
of each new part ⊗4must⊗* be known in order to safely  inject  a  new
BEING.
This may be a result of the small amount of knowledge in PUP6. One would
hope that a BEINGs system which was expert in a domain could assist the
user in adding new domain-specific BEINGs, in the same way that the
BEINGs which make up the target code are synthesized, through dialogue.

To modify PUP6 to synthesize new inductive inference programs
similar to CF,
it would probably be necessary -- and sufficient --  to add a few
general-purpose programming and communication BEINGs, 
plus add several 
BEINGs specific to the new program's domain, plus
generalize a few existing BEINGs' parts.
The dialogue to produce the new program may
be poorly suited to that program, since most of the
recognized phrases stem from a single (CF-producing) protocol.

To improve PUP6's performance, one could add some debugging 
specialist BEINGs, some dialogue specialists, 
some sophisticated User-psychology experts (why is the user
asking me that question, what needn't I tell him, how should I direct his
attention), some BEINGs whose task is to aid the untrained user in inserting new
domain-specific BEINGs, and perhaps a whole library of varied specialist BEINGs.

.SSEC(About Automatic Programming)

	The need for flexible communication stems  only
partially from inter-user  differences.   A  serious  and  unexpected
source  of  conflict  here  is the amount of inference the user wants
done.  This level is relatively subjective, and may fluctuate rapidly
even  with  one  user  writing one program. Perhaps there should be a
dial he can set. At one extreme, the system would  ask  the  user  to
verify  even  the  most  trivial  inductions.  At  the  other extreme
setting, the system would probably write  the  target  program  after
just a few brief user inputs. The user would then try out one program
after another, interjecting just one or two comments each time, after
which  the  system would come up with the next version.  This program
modification mode seems appropriate for someone ignorant of LISP, who
nevertheless has the I/O behavior of his target clearly in mind.
	Much  of PUP6's comments are boring and unnecessary; this was
felt to be an engineering problem which would be ignored in all but a
"marketable"  AP (automatic programming) system. 
This view was probably incorrect. One of the
most severe AP problems is having  the  system  inform  the  user  of
precisely  what  he should know -- no more nor less.  This requires a
sophisticated  user  model  cleverly  interfaced   to   the   current
programming task.
	Another problem with large, long dialogues is user  error.  A
human  has  great  difficulty keeping "on top" of everything.  He may
get lost, forget, change his  mind,  or  misunderstand.  Again,  this
problem  was originally considered ignorable, but has shown itself to
be  a  limiting  practical  factor  in  wide  accessability.  It  was
necessary  to  create  a  forgetful-user  demon  to prevent anaphoric
reference to something which, though uniquely determined, hadn't been
mentioned within the past several seconds.
Related to this is the problem of keeping
the user informed of where he is. PUP6 simulated a continuous display
of  the graph of the current partial program, augmented by static and
dynamic cursors. This  simple 
use  of  dynamic  and  textual  indices  seems
insufficient.   The  user was still often confused, wishing a section
referred to not by pointing but rather by a brief, meaningful (to him
only!)  phrase.   This may also be one of the major AP problems which
must be studied further.
	These  worries  about large dialogues arise because future AP
systems are viewed as tools for writing programs which humans  simply
cannot  manage  currently:      viable natural language systems, huge
operating systems, better AP systems.
	One might argue against ever needing a
system whose target programs will be longer and more complex than the
system  itself.  First,  empirically, optimizing compilers are viable
and yet they dwarf almost all the code they generate.  Second, as the
complexity  of the transformation increases, the length of a compiler
increases rapidly.  For a truly intelligent AP system, one  might  be
willing  to  tolerate a program several times as large 
and as complicated
as anything it
could produce.
	An  argument  exists  to  counter this one.  First, one might
object to restricting the analogy to  compilers;  many  entities  are
capable  of  producing  things  more  sophisticated  than themselves,
larger than themselves, etc. (consider evolution). Second,  it  seems
that there is a manageable body of information which one needs master
to do programming.  Viewed differently, one can
write  programs  as huge as he wishes if the program is designed in a
clean way. Thus the size of AP systems will probably
level  off  (albeit  huge
compared  to  existing  programs)  even as the size and complexity of
their generated code continues to increase and,  eventually,  surpass
them.  Finally,  we  must  consider why we want a good AP system:  to
help  us  write  large  programs  easily,  programs  which  might  be
unmanageable  today.   For  this  reason alone, our AP system must be
able to deal with programs larger than itself.


	Good measures  of  concentration  of intelligence are not yet
available, even for a restricted domain like automatic programming.
Earlier, we compared system size and target program size. Such a crude
measure omits two very important factors:
First, one might improve any such measure by simply
decreasing the size of a given system. This is wrong, since, e.g., 
removing all the comments from a program shouldn't increase its
intelligence!  Secondly, the total amount of distinct target programs
should be considered. Compilers turn out programs small compared to
themselves, but are valuable because of the vast variety of such programs
they can put together.
This factor reflects how much of the "guts" of the system can be used in
writing many programs.
The  second  and third programs were attempted
only to test its flexibility, and the results were mixed.



.SSEC(About BEINGs)

Let us step back for a moment to place our hopes in perspective.
Many  researchers  feel
that a simple, uniform formalism should be used for all facts; others
disagree, claiming that complexity of  behavior  both  justifies  and
demands complexity of representation.  
The  benefits  of  the  uniformity include  (i) easy
addition  of  knowledge  [Newell]  and  (ii) simple, aesthetic methods for
combining information [McCarthy]. Structure,  however,  is  necessary
for (⊗4combinatorially⊗*) efficient handling of large amounts of data
(see the real world; also [MIT]). 
⊗7The disadvantages of uniformity are the inefficencies of dealing with
massive amounts of information; often one finds encodings of more complex
structures (e.g., when Newell arduously simulates sequential processing
by chaining productions). The disadvantages of highly structured representations
include the difficulty of modifying the system, the amount of expertise demanded to
add a new piece of information.⊗*

.ONCE TURN ON "{}"
The BEINGs concept certainly doesn't resolve
this uniformity vs.  structure controversy, yet it is a sort of
compromise.  While BEINGs have a complex structure, that structure is
uniform over all BEINGs.   
The number of BEING parts (each BEING has the same number of parts) indicates
the mixture of structure and uniformity in the system (this was discussed near
the end of section 8, on page {MIXPAGE}.
Just as the design of BEINGs is theoretically a mix, a compromise, so
the ⊗4performance⊗* of the BEINGs representation itself in PUP6 is mixed.
Of the two advantages hoped for by using a uniform set of BEING parts,
(i) addition of new BEINGs to the pool was ⊗4not⊗* easy (for untrained users)
but (ii) communication among
BEINGs ⊗4was⊗* easy (fast, natural). Of the two
advantages hoped for by keeping the BEINGs highly structured,
(i) the interactions (especially with the user) were distastefully
brittle, but (ii)
the complex tasks put to the pool ⊗4were⊗* successfully completed.

The crippling problems are seen to be with user-system communication,
not with the BEINGs ideas themselves.
Sophisticated, bug-free programs ⊗4were⊗* generated, after hours of fairly high
level dialogue with an active user, after tens of thousands of messages passed
among the BEINGs.
Part of this success is attributed to distributing
the responsibility for writing code and for recognizing relevance, to a hundred
entities, rather than having a few central monitors worry about everything.
The standardization of parts made filling in the BEINGs' contents fairly painless.

All this suggests two possible continuations, both of which are underway here
at the Stanford AI Lab. One is to
rethink the communication problems,
and develop a new system for the
concept formation program synthesis task. The earliest programs by our group [1]
were aimed at getting the target program; this research insisted on getting the
target program by going through one "proper" sequence of reasoning steps; 
the proposed continuation wants several
untrained users to  succeed by many different "proper" routes.

 
The other way of continuing
is to find a task where BEINGs are well-suited, where
the problems encountered in PUP6 won't recur. What ⊗4are⊗* BEINGs good for?
The idea of a fixed set of parts (which distinguishes them from ACTORs) is
useful if the mass of knowledge is 
too huge for one individual to keep "on top" of.
It then should be organized in a
very uniform way (to simplify preparing it for storage), 
yet it must also be highly structured
(to speed up retrieval). In fact, BEINGs can 
be utilized within the usual solution to a
large problem: a group project. The members split apart after agreeing
on what the set of parts is to be. 
In selecting the continuation, the problems in this research should be isolated
from the staggering complexities of natural
language handling. For these reasons, the author is currently
investigating elementary number theory as a potential task domain.
BEINGs are big and slow, but valuable for organizing knowledge in ways 
meaningful to how it will be used. In future systems, BEINGs will be one
-- but not the only -- 
internal mechanism for representing and manipulating knowledge.
.ASEC(References)

[Balzer] Balzer, Robert, "AIRLINE reserv. study...," 197..

[Bobrow] Bobrow, Daniel, and Raphael, Bertram, ⊗4"New Programming
Languages for
AI Research⊗*," XEROX Research Report CSL-73-2, August 20, 1973.

[Charniak] Charniak, Eugene, "⊗4Jack and Janet in Search of a
Theory of Knowledge⊗*," 3rd IJCAI, 1973, pp. 337-343.

[Dijkstra] Dijkstra, Dahl, and Hoare, ⊗4Structured Programming⊗*,
197..

[Dreyfus] Dreyfus, Hubert, "⊗4Alchemy and Artificial Intelligence⊗*,"
196...

[Fikes] Fikes, Hart, and Nilsson, "⊗4Learning and Executing
Generalized Robot Plans⊗*," Artificial Intelligence, Vol. 3,
Winter, 1972.

[Floyd] Floyd, Robert, "⊗4Toward Interactive Design of Correct 
Programs⊗*," IFIP 1971, V. 1, pp. 7-10.

[Gadwa] Gadwa, Peter, "⊗4SPOT, a mini concept formation program⊗*,"
Unpublished Master's Thesis, SAIL, August, 1973.

[Green]
Green, Waldinger, Barstow, Elschlager, Lenat, McCune, Shaw, and Steinberg,
⊗4Progress Report on Program-Understanding Systems⊗*, Memo AIM-240,
CS Report STAN-CS-74-444,Artificial Intelligence Laboratory,
Stanford University, August, 1974.


[Hempel] Hempel, Carl G., ⊗4Fundamentals of Concept Formation in
Empirical Science⊗*, University of Chicago, Chicago, Illinois,
1952.

[Hewitt] Hewitt, Carl, "⊗4A Universal Modular ACTOR Formalism for
Artificial Intelligence⊗*," 3rd IJCAI, 1973, pp. 235-245.

[Kant] Kant, Immanuel, ⊗4Prolegomena to any Future
Metaphysics⊗*.  Kant points out that concept formation and
grammatical inference are merely different faces of inductive
inference.

[Luckham] Luckham, David, and Buchanan, Jack, "⊗4On Automating the
Construction of Programs⊗*," SAIL AI Memo 236, May, 1974.

[McCarthy] McCarthy, John,and Hayes, p., "⊗4Some Philosophical 
Problems From the
Standpoint of Artificial Intelligence⊗*," Machine Intelligence 4,
pp. 463-502.

[MIT] Minsky, Marvin, and Papert, Seymour, ⊗4Artificial
Intelligence Progress Report⊗*, MIT Project MAC, AI Memo
252, 1972.

[MIT2] Winston, P., (ed.),
"New Progress in Artificial Intelligence",
⊗4MIT AI Lab Memo AI-TR-310⊗*, June, 1974. 
Note especially the summaries of work on Frames,
Demons, Hacker, Heterarchy, Dialogue, and Belief.

[Newell] Newell, Allen, and Simon, Herbert, 
⊗4Human Problem Solving⊗*, 1973.

[Pilvar] Pilvar and Frank???, Seq.Extrap. Article, ⊗4LISP Studies⊗*,
19.., pp. ...

[Poincare'] Poincare', Henri, ⊗4The Foundations of Science⊗*, translated
in 1913 by Bruce Halstead. The concept of procedural representation of
knowledge is p. 246 ff., in the 1929 edition, The Science Press, N.Y.

[Reboh] Reboh, Rene, and Sacerdoti, Earl, ⊗4A Preliminary QLISP
Manual⊗*, Technical Note 81, Artificial Intelligence Center, 
SRI, Menlo Park, California, August, 1973.

[Reddy] Erman, Fennell, Lesser, and Reddy, "⊗4System Organization
for Speech Understanding⊗*," in "Working Papers in Speech
Recognition," CMU CS Speech Group, August, 1973.

[Rulifson] Rulison, Jeff, and... ⊗4QA4, A Procedural Frob...⊗*,
Technical Note..., Artificial Intelligence Center, SRI, Menlo
Park, California, ..., 1973.

[Teitelman] Teitelman, Warren, ⊗4INTERLISP Reference
Manual⊗*, XEROX PARC, 1974.

[Winograd] Winograd, Terry, "⊗4Understanding Natural Language⊗*,"
Ph.D. Dissertation, MIT, 1971.

[Winston] Winston, Patrick, ⊗4Learning Structural Descriptions
from Examples⊗*, Ph.D. thesis, Dept. of Electrical Engineering,
TR-76, Project MAC, TR-231, Artificial Intelligence Laboratory,
Massachusetts Institute of Technology, Cambridge, Massachusetts,
September, 1970.

[Woods] Woods, W.A., and Makhoul, J., "⊗4Mechanical Inference
Problems in
Continuous Speech Understanding⊗*, Third International Joint Conference
on Artificial Intelligence, 1973, pp. 200-207.

.SSEC(Acknowledgements)

This document contains material found in four recent papers by the author:
⊗4Synthesis of Large Programs by Specific Dialogues⊗*, Symposium on Proving
and Improving Programs, France, July, 1975;
⊗4Duplication of Humans Activity by Interacting Knowledge Modules⊗*,
3rd Congress on Systems and Cybernetics, Roumania, August, 1975; 
⊗4BEINGs: Knowledge as Interacting Experts⊗*, 4th IJCAI, USSR, September, 1975;
and [Green], above. Many new details are revealed here, and almost all the material
in the appendices has not been presented previously.

The ideas and the system described are built upon recent researches by many others
(⊗4sic,⊗* the references above). Many
hours of creative discussions were equally important.
In particular, the author  acknowledges the contributions by
C. Green, R. Waldinger, D. Barstow, E. Sacerdoti, and D. Shaw.
Computer time for the research was generously provided by the Artificial
Intelligence Center of SRI.

.EVERY HEADING(⊗7{DATE}     D.  Lenat,BEINGs.... {SECTION},page {PAGE}⊗*)
.ASEC(Appendix 1: Values of parts of a typical BEING)

.ONCE TURN ON "{}"
	We consider 
⊗6INFO-OBTAINER⊗*, a BEING which is independent of task domain.
Below is listed, for each part, its abbreviated name (in bold),
an English question that it might (try to) answer, 
an answer it might provide to that question (in italics),
the stored program which is evaluated to produce that answer
(often a simple template or a constant),
and occasionally a brief explanation.
Compare these actual values for the parts to the assembled function on page {FPAGE}.

.BB

⊗2WHAT⊗*  Basically, what do you do?  ⊗4I obtain some information which can be used.⊗*
	(Obtain some information which can be used) 
⊗2WHY⊗*	 Why do you do this?  ⊗4Because PUP6 has no more information that is immediately usable.⊗*
	(PUP6 has no more information that (1) is immediately usable (2) it can use to progress) 
⊗2HOW⊗*  How do you do this? ⊗4Obtain new facts about old information.⊗*
		How else? ⊗4Obtain totally new information.⊗*  How else? ⊗4No other way.⊗*
	((1) Obtain new facts about old information, (2) obtain totally new info)
.E
The above three parts are present mainly for the user's benefit. 
In the current case, they don't even have any uninstantiated subparts. If the user
asks one of these three questions when INFO-OBTAINER is in control, then the appropriate
answer is simply typed out.

.BB
⊗2IDEN⊗*  Can you recognize this phrase: "Find out more about frob gyrnation"?
	⊗4Yes.  Call me with "frobs" as the argument.⊗*
	((if you see: (INFO-OBTAINER any1)   then return: (INFO-OBTAINER (TRANSLATE any1)))
	 (if you see: (FIND OUT MORE ABOUT any1)   then return: (INFO-OBTAINER any1)))
.E
This BEING possesses just two simple <template>→<transformation> translation productions.
In the first case, if the argument pattern matches the template, we first call
TRANSLATE recursively on a subpart of the pattern, then call INFO-OBTAINER on that
result.

.BB
⊗2EXPLICIT-ARGS⊗*    	What argument(s) do you take?   ⊗4The single argument "U".⊗*  ( U )
⊗2EVAL-ARGS⊗*	   Which arg(s) are quoted, not evaluated?  ⊗4None.⊗*    NIL
⊗2IMPLICIT-ARGS⊗*  What local variables are needed?  ⊗4None.⊗*   NIL
.E
There is only one argument to INFO-OBTAINER.  It is never operated upon, so nothing
much need be known about it. It is simply relayed to other BEINGs called by INFO-OBTAINER.

.BB
⊗2WHEN⊗*    How badly do you want to take control now (justify your answer)?
	⊗4My overall rating is +95, quite high, because there are 5 pieces of new information.⊗*
	((if T then add in -10 because (I AM EXPONENTIALLY-GROWING, GENERALLY UNDESIRABLE))
	 (if NEW-INFO-LIST then add in  (PLUS  100  (LENGTH  NEW-INFO-LIST))
	       	because (WE SHOULD WORK ON UNASSIMILATED NEW  INFORMATION IF THERE IS ANY)))
.E
The WHEN part of a BEING is a collection of triples: if <predicate> then
<value> because <reason>.  If the <predicate> evaluates to non-null, then
the <value> program is executed. It returns a number, which is then added
together with the other factors' numbers to produce a rough estimate of
how a propos this BEING is to take control right now.  The <reason>
evaluates to an English phrase, for the benefit of inquisitive users.
This linear scheme is undesirable but (sigh) adequate. The first factor
here says to always add in the number -10; the second says
if there is some new information sitting around unexploited, to add in 100
plus the number of such pieces.
These factors and their weights, like the contents of all the parts
of all the BEINGs initially in the experimental PUP6 system, 
were decided upon and inserted by
hand.

.BB
⊗2META-CODE⊗*  When you are in control, what specifically do you do to acheive your results?
	⊗4I have 4 specific BEINGs decide among themselves who goes next.⊗*
	Why? ⊗4Because we can only try to obtain usable information in one way at a time.⊗*
	(DO
	       (CHOOSE-FROM ((GET-NEW-INFORMATION U)
	  	    	          (TRANSLATE U)
		                  (ANALYZE-IMPLICATIONS U)
				  (EXTRACT-RELEVANT-SUBSET U)))
          BECAUSE
	        (WE CAN ONLY TRY TO OBTAIN USABLE INFORMATION IN ONE WAY AT A TIME))
.E
This part says that all INFO-OBTAINER does is to pass control to one of a certain
group of four BEINGs: (1) Get brand new information, from the user via translation
or from known knowledge via inference; (2) Translate something, transform an English
phrase into BEING calls (if you're lucky); (3) Analyze the ramifications of some
particular piece of existing, translated knowledge; (4) Extract a small, relevant
subset of a chunk of information, and concentrate upon that small piece.
INFOR-OBTAINER passes control to CHOSE-FROM because the set of possible choices for
control recipient is explicitly known. More frequently, a BEING will know only some
descriptionof what it wants, and will then call SATISFY, who will locate all the
potentially relevant BEINGS, and then call CHOOSE-FROM. A third alternative would be
to call the desired successor by name, if that name were known.

.BB
⊗2MAIN-EFFECTS⊗* Who can cause this to occur: "Usable information exists"? ⊗4I can do it.⊗*
	Who can cause this to occur: "The time of day is known."  ⊗4I don't know who can do it.⊗*
	((to get (NEW INFORMATION any1)       do (INFO-OBTAINER any1))
	 (to get (USABLE INFORMATION any1)   do (INFO-OBTAINER any1)))
⊗2AFFECTS⊗*     Might you call on TRANSLATE directly? ⊗4Possibly.⊗*
	((CHOOSE-FROM is called)
	 (some BEING who can cause (AWARE USER (ABOUT TO OBTAIN USABLE INFO)) is called)
	 (GET-NEW-INFORMATION possibly is called)
	 (TRANSLATE possibly is called)
	 (ANALYZE-IMPLICATIONS possibly is called)
	 (EXTRACT-RELEVANT-SUBSET possibly is called) )
⊗2COMPLEXITY-VECTOR⊗*  What is your % chance of failing? ⊗410%.⊗* (.5 .3 .1 .4 .2) 
.E
The first component says that ⊗6INFO-OBTAINER⊗* is of typical (.5)
difficulty to call. Next, there exists a .3 chance that some descendant
will call it again. The third component indicates that this activity almost
always succeeds. The time/space used in allowing this BEING to try
is slightly better than average. Finally, there is no good reason (.2) 
for inhibiting
it ever.  In general, each component can be a ⊗4program⊗*,
not just a constant.

.BB
⊗2GENERALIZATIONS⊗*   What BEINGs are more general than you?   ⊗4Write-program and Serve-the-user.⊗*
	(WRITE-PROGRAM  SERVE-THE-USER)
⊗2ALTERNATIVES⊗*   Is OPTIMIZE similar to you, an alternative in case you fail?  ⊗4Yes.⊗*
	(USE-INFORMATION  FIX-INCORRECT-PIECE  OPTIMIZE  FILL-IN-UNDEFINED-SECTION)
.E
If this BEING fails, try some of its alterntives. If they fail, consider trying some
more general (but weaker) BEINGs.
.ASEC(Appendix 2: The BEINGs present in PUP6)
.SELECT 1

Here we present summaries of the knowledge embedded  in  each  BEING.
Only  the  most  important  parts  of  each BEING are even mentioned.
First we present those BEINGS used to write CF. Next come the ones we
had  to  add  to the pool to get PUP6 to write GI and INF.  Among the
first  group,  we  further  subdivide   it   into   (a)   high-level,
domain-specific,   (b)  low-level  domain-specific,  (c)  ubiquitous,
domain-independent,   (d)   high-level,   domain-independent,   (e)
low-level, domain-independent, (f) non-BEING knowledge in variables,
and (g) a  few  interesting  demons  and  functions.   The  number of
additional BEINGs to write GI and  PL
is so small we don't subdivide their descriptions.


.SSEC(The knowledge necessary to write a concept formation program)

	⊗5A. High-level, domain-specific knowledge⊗*


⊗4CONCEPT-FORMATION⊗*. 
Each interesting BEING part is translated into English. Just this once,
the name of the part will be (parenthesized) preceding the translation.
(pre-requisite:)
The user must be aware that we  are  about  to
undertake concept formation. 
(demons:) Inference and attention-focussing demons
must be turned on. 
(effects:) After completion of this task, PUP6 will  be  able
to learn concepts. 
(generalizations:) This is a specialized form of attending, learning,
and doing inductive inference. 
(alternatives:) It is an  alternative  to  grammatical
inference,   pattern   recognition,   and  simulated  evolution. 
(specializations:) Its
structure must  be  one  of  the  following:  classificatory  concept
formation,   comparative   concept  formation,  or  metrical  concept
formation. We must make the boolean decision as  to  whether  or  not
concepts  may  vary  with  time.  Similarly,  whether  the  speed  of
presentation of  the  stimuli  is  relevant;  if  so,  then  we  must
constrain  the  effort  spent  on  various  phases of identification.
Instances may be left in view indefinitely, or may be  removed  right
after  processing;  this  latter  case holds for CF; it means we must
derive all relations (features) as  soon  as  we  see  a  scene.  The
program  will  have  to be just complex enough to handle conjunctive,
disjunctive, or both kinds of concepts; this is another  decision  to
make.  Similarly  for  positive,  negative, both, or neither kinds of
transfer  (psychological),  which  affects  the  recognition  that  a
concept is new, and how previously learned concepts interact with the
learning of new ones.   We  must  decide  whether  to  use  positive,
negative,  or  both kinds of instances of a concept. Subject-specific
behavior may be required; that is, the program may have  to  input  a
vector  describing  a  particular individual, and its whole structure
must mimic this subject. The last decision is  one  of  adapting  the
program  to  an extended sample dialogue which the user must furnish;
this will help both to check out the program  writtten,  and  to  fix
various  print  statements  and  I/O formats. 
(complexity-vector:) It is easy to call this
BEING (.1), it has a 50-50 chance of calling* itself, it has  only  a
0.5  chance of succeeding, but the effort to try it is moderate (.5).
There is no fundamental reason for delaying its  investigation  (.1).
(iden:) It  recognizes  
itself  only  through  exact matching of one of seven
patterns. (what, how, why:) 
It has sentences describing what it does, how, and why. (when:) It
is  unlikely  (-70) to be called if some type of concept formation is
already doable by PUP6; if PUP6 wants to characterize  classes,  then
it's  very  likely (88) to be called. The presence of new information
delays (-60) our calling the BEING, since it  might  affect  what  we
should  do.  Conversely,  the  absence of new information mildly (40)
encourages us to go on and try it. 
(post-requisites:) When finished, the  user  must  be
aware  that  PUP6  has  decided  on  a  particular  type  of  concept
formation, and that it has done it. (affects:) 
The other BEINGs affected  depend
on the decisions mentioned earlier.

	This is an over-abundance of information. From now on, I will
only give the little pieces of information which are crucial  to  the
BEING; its essence. Also, the BEING part names won't be explicitly
provided.

⊗4CLASSIFICATORY CONCEPT FORMATION⊗*. To do this, we must partition a
domain, in an interactive "guessing" manner.

⊗4COMPARITIVE CONCEPT FORMATION⊗*. Same as above, but  then  we  must
partially  order  the  equivalence  classes  of  the partition. It is
harder, also.

⊗4METRICAL CONCEPT FORMATION⊗*. Same as previous BEING, but  we  must
also  induce a metric on the partial ordering of the classes. This is
even more complicated.

	Since we actually do classificatory CF, the BEINGs to order a
partition and to metrize an ordering weren't implemented.

⊗4PARTITION  A  DOMAIN⊗*  in  a  guessing,  interactive  manner.  The
partition may be only  partial,  it  may  be  only  weak,  and,  most
crucially,  the  BEING must be able to do some of these: partition by
accepting an element and getting its class name  (guessing  the  name
and  then  checking  it somehow), partition by accepting a class name
and getting its member elements, partition by accepting ordered pairs
<element,  classname>.   The  fringe  of  consciousness  demon must be
activated from now on.

⊗4PARTITION BY TAKE ELEMENT GET CLASS⊗*. Take hold of an element  (by
reading,  for example), and then work to get the name of the class it
belongs to (by guessing, then verifying the guess, for example). Then
modify the structure of the class(es) involved.

⊗4PARTITION  BY  TAKE  CLASS GET ELEMENT⊗*. Take hold of a class name,
and then work to get elements it contains. Then modify the  structure
of the class and the element(s) involved.

⊗4PARTITION BY TAKE ELEMENT AND CLASS⊗* simultaneously. Take hold of
both an element and its corresponding class name, and  use  these  to
modify  the  structure  of  the  partition;  i.e.,  modify  the class
mentioned if the partition is stored by classes.


	⊗5B. Low-level, domain-specific knowledge⊗*

⊗4RECOGNIZE  CONTRADICTION⊗*.  It  can translate "... is incompatible
with ...". It is a predicate, fairly easy to write therefore.  It  is
composed   of  SOMEOF  the  following:  Probability≡0  contradiction,
Probability≡1 contradiction, Probability  >0  and  <1  contradiction.
Since  these names are fairly cryptic, some of their parts (e.g, HOW)
must be printed out to  help  the  user  choose  (whenever  they  are
involved, if the user asks for ramifications.)

⊗4PROBABILITY  ≡ 0 CONTRADICITON⊗*. Since this is a very simple thing
in our domain of concept formation, it is  immediately  encodable  as
(MEMBER  arg1  arg2).  That  is,  if  arg1  has  probability  zero of
occurring in arg2, yet it does, then we have a contradiction.

⊗4PROBABILITY ≡ 1  CONTRADICTION⊗*.  Immediately  encodable  as  (NOT
(MEMBER  arg1  arg2)).  If  arg1  has probability one of occurring in
arg2, yet it doesn't, then we have a contradiction.

⊗4PROBABILITY >0 AND <1 CONTRADICTION⊗*.  Immediately  enacodable  as
NIL.  If  arg1  might  and  might  not  occur in arg2, we can't get a
contradiction just by checking its membership. Of  course,  the  idea
that  this is the only way to prove contradiction is what makes these
BEINGs domain-specific!

⊗4SCENE⊗*. This is a data structure, composed of four subparts.  The
first is a set O of objects. Next is an atom indicating the name N of
the scene. Next come two lists of features, where a feature is just a
predicate  and  its  arguments.  The  first is the static relations S
between objects. Finally we have  the  dynamic  relations  D  between
objects.

	⊗5C. Ubiquitous, problem-independent BEINGs and functions⊗*

⊗4CHOOSE  FROM⊗*.  All its arguments must be BEINGs, else it prints a
nasty warning message. We select the best BEING and apply it.  If  it
fails,  we  re-order  the  remaining BEINGs and apply the best one of
them. Note that this new reordering may use knowledge gleaned  during
the  earlier,  unsuccessful  BEING  try.   Thus, this is a (possible)
intelligent nondeterministic branch point. The intelligence lies  (or
fails  to  lie) in the comparison function, BETTER, which decides who
goes next.

⊗4SATISFY⊗*. This  is  the  equivalent  of  a  pattern-directed  goal
statement.  We ask each BEING, "Can you do anything matching x?".  We
take the list of those answering affirmatively, and  CHOOSE  FROM  it
one  BEING  after  another  until  the  desired effects are realized.
Notice  that  a  BEING  who  said  "probably"  may  succeed  in   his
application  and  yet  not  effect  the  result  we wanted, so that a
trivial call on CHOOSE FROM  is  insufficient.  The  BEINGs  possibly
affected are just those answering affirmatively.

⊗4MESSAGE⊗*.  This  BEING  has a main effect (AWARE USER x), hence is
very frequently called.  The forgetful-user  demon  trims  the  aware
user  list  periodically.  Message  looks to see if its message is on
that list; if not, it inserts it and prints it out to the user. If it
is,  it  moves  the  message  to the front of the aware-user list and
prints out nothing. This  is  an  example  of  a  specialized,  fixed
assertion-list, as described earlier.

⊗4DETERMINE ARG VALUES⊗*. These functions take as input the name of a
function, and output a description of what arguments it will ever  be
called  with  (in the existing code.) For example, it might say "arg1
will always be NAME-OF-CLASS, and  arg2  will  consecutively  be  all
integers from 3 to (LENGTH SET-OF-CLASSES)". At present these work in
the obvious way, looking at everything. The tremendous amount of  CPU
time  spent  in  these  functions  indicates  that I should have made
special assert-lists for argument instantiations,  and  updated  them
each time a BEING is called in the target code.

⊗4FLOW-PRECEDED⊗*.  This  BEING must search through he code to find a
form matching a given pattern.  Although it is used under  ten  times
in  the  total dialog, it is so costly that I've implemented it as an
ask-the-user call. Work must be done here to understand why  this  is
so inefficient, and to remedy it.

⊗4FIND AND TAG⊗*. This BEING is similar to flow-preceded, except that
the pattern-matching  is  between  two  constant  strings.   This  is
tolerably  efficient  in  CPU time and is used heavily throughout the
writing of CF.

⊗4TRANSLATE⊗*. The natural language front  end  is  managed  by  this
BEING.  It  asks  each  BEING  whether  it recognizes a given string.
Translate then takes the "best" -- the most probable -- of  these  as
the   translation,  and  can  backtrack  and  reorder  the  remaining
interpretations if it has to. If called with no argument, it examines
various  assert-lists  to  see if it can do any good. The idiom demon
must be activated during the control period of this BEING.

⊗4REINVESTIGATE DECISION⊗*. This is usaully called  by  a  demon  who
watches  the  deferred-decision assert list. We transfer the decision
in question from the deferred to the undeferred decision assert list.
A deferral demon will promptly react to anything on this latter list.
An interesting caution: it was necessary to inhibit all demons during
the  execution  of  this  BEING,  for  reasons  very similar to those
leading to lock and unlock system commands. The fact that some  BEING
might  have  to  be  demon-uninterruptable  forced us to institute an
entire new question asking just about this tiny point!

⊗4DEFER DECISION⊗*. Remove the decision from the undeferred  decision
assert  list. Determine the situation when we must next reinvestigate
this decision. This will be some predicate examing the state  of  the
world.  If  this  predicate  is  true  currently, we must resolve the
decision now. Otherwise, we put the decision on the deferred decision
list, attached to its (new) reinvestigation predicate. Demons must be
inhibited during this BEING's reign, to ensure that  its  notions  of
the world are accurate upon exit.

⊗4WHEN  NEXT⊗*.  Manipulate  the  decision to extract the name of the
variable holding information  relevant  to  deferring  the  decision.
Utilize  this  knowledge  so  as  to keep the effects of the decision
irrelevant; i.e., find the (next) situation in  which  they  are  not
irrelevant.  Whoever called this BEING is now asserted to be aware of
its results. This is fairly complex, and  the  BEING  is  not  called
unless  it  is necessary. As it happens, it is called a few times for
every decision to be made about every BEING  in  the  target  program
(several hundred times).

⊗4UTILIZE⊗*.   This  BEING  applies  various  knowledge  "variables,"
starting at specific ones and moving toward very general ones,  until
one of them reports it is able to acheive the desired goal.

⊗4RESOLVE DECISION⊗*. Again, all demons must be inhibited. After some
preliminary searching and very  trivial  theorem-proving  fail,  this
BEING  resorts  to  asking  the  user  about  how  to resolve a given
decision.

⊗4ASK USER ABOUT⊗*. We determine the argument instantiations  of  the
little  piece  of  code  we're  worrying about, determine the type of
decision to be made, and apply the specific  knowledge  variable  for
x-ing  that  type  of  decision. Here, we get x by examing who called
this BEING and why. To write a specialized version of ask-user-about,
we  just  write a standard print, read, and assign function, with the
details left unspecified until the sample session is read in.

⊗4BETTER⊗*. This function is used to compare two BEINGs,  and  decide
which  of  them  should gain control.  It evaluates their WHEN parts,
and if they tie it evaluates  their  complexity  vectors.  Note  that
"eval"  here  is not trivial: each dimension of the complexity vector
of a BEING can be a  little  program  which  examines  itself,  other
BEINGs,  and  the  state  of the world before deciding on a numerical
answer to return.

⊗5Handling of User Interrupts⊗*.  There  are  several  functions  and
BEINGs  involved  in  this process. Initially, the user describes how
often the system is to give him  the  opportunity  to  interrupt  and
query it.  At each of these times, the HANDLE USER INTERRUPT function
asks the user if he wants to interrupt; if so, PROCESS USER INTERRUPT
is  called  to  do  the  job. In addition to asking for pieces of any
BEING, the user may request limited simulated  execution  of  various
pieces, and may order the current BEING to FAIL.



	⊗5D.  High-level, problem-independent knowledge: how to write
programs⊗*

⊗4SERVE⊗*. Obtain information until some of it is "executable,"  then
carry  it  out.  The  forgetful-user demon is activated. Without this
top-level purpose, PUP6 sits contentedly, never wanting to  accept  a
new task.

⊗4WRITE  PROGRAM⊗*. The user must be made aware that PUP6 is about to
write a program, what kind of program it is, what its name  is  (this
will  force  a  get-name  BEING  call),  and  that  its type has been
examined (this will cause a study-type BEING  call).  Upon  exit,  he
must  be  told  that  PUP6  has  completed the task, and what its new
capabilities are. To wite a program, one enters a loop,  broken  only
when  several  completion conditions are all true simultaneously: the
top-level task is now a BEING, there are  no  undefined  sections  of
code,  there  are  no  warnings  left  about  the  code,  there is no
executable information anywhere, there  is  no  new  but  unprocessed
information,  there  are  no  decisions  still  pending (except those
requiring "everything else" to be complete; e.g., the  adaptation  of
output  formats  using  a  sample session). If we do break out of the
loop, we must update the list of programs written,
the list  of  what
PUP6  can now do, the list of what the user may do, and then we must
gather up the relevant new BEINGs and 
dump them onto a file. This latter
task is done by SUPPORT&DUMP.
In general,
of  course, we won't break out, so we activate all the current demons
and go on. All the body of the loop is is one  CHOOSE  FROM,  between
six alternatives: obtaining some usable info, using some usable info,
filling  in  some  function  call  which  is   currently   undefined,
clarifying  some little piece of code known to be improbable for some
specific reason, adapting some known  function  to  conform  to  some
specific  new  requirements,  fixing some piece of code which doesn't
work the way it claims to work. The last  two  of  these  are  simply
program  modification  and debugging, respectively! Failure of one of
these six BEINGs simply causes CHOOSEFROM to try another one; failure
of  a  demon causes the whole WRITE PROGRAM BEING to fail. During its
reign,    the    program-writing    demons,    deferral-demon,    and
reinvestigation-demon  are  all  activated.  Its complexity vector is
dependent upon that of the BEING closest to the task it must perform.

⊗4SUPPORT&DUMP⊗*. We find the set of support
of the top-level task  and  create  a  new  file  with  the  relevant
functions and BEINGs (which automatically does global initializations
and then enters the top-level task instead of SERVE). The user is 
informed of all this, and allowed to interrupt and ask questions.

⊗4OBTAIN USABLE INFORMATION⊗*. The WHEN part informs us that this  is
always  undesirable (-10) but is OK (111) if there exists new but not
yet usable information. All we do here is CHOOSE FROM  the  following
four  alternatives:  translate  something, get brand new information,
analyze the implications of existing  information,  extract  a  small
relevant subset of the existing information to concentrate on.

⊗4USE  INFORMATION⊗*.  This  demands that some executable information
exist. We select one such piece, and try to execute it. If  we  fail,
its  worth  is  decreased;  if  we  succeed,  it  is removed from the
executable info assert list.

⊗4FILL IN UNDEFINED SECTION⊗*. There must be some undefined  section.
If  so (80) we don't want any hi-priority (⊗6≤⊗*20) coding warnings still
around (-150), and we do like there to be  something  both  undefined
and  known  to  be encodable (96). We fix a choice of what to encode,
and try to acheive its encoding. If we fail, we update the difficulty
of  that  choice,  and  may  assert  that  we  want some specific new
information to relieve the problem.   In  addition  to  ENCODE,  this
BEING also may call MAKE ENCODABLE and STUDY TYPE.

⊗4CLARIFY  IMPROBABLE  SITUATION⊗*. This BEING demands that something
of mediocre priority (⊗6≤⊗*500) exist on the coding warning  assert-list.
It  likes  (51)  this,  and  dislikes (-41) anything on the undefined
section list, or anything (-200) on the encodable section  list.   As
always,  a  sentence  is  provided  to  justify  each of these little
beliefs. We choose the warning  with  the  highest  priority  (lowest
numerical  weight) on the coding warning list, note that that is what
PUP6 is working on now, and do a match to decide what type of warning
it  is. (i) Replace x by y in z. Here these may be nonspecific; z may
be "in all code recently generated". The nature of y may cause us  to
include new warnings; y may mention a new data structure. (ii) x in y
is undefined; probably z since r. This may cause us  to  add  to  the
global initialization list. It will probably cause us to ask the user
what the answer is. (iii) x is a data structure  but  we  don't  know
much  about  it. We try to find out its structure, how to initialize,
access, insert, delete, update it. A variant of this warning is: (iv)
We  find no x's associated with data structure y. Here x can point to
insertions, deletions, initializations, etc. If we can't justify  the
lack,  we  try  to defer the decision. Failing that, we ask the user.
(v) Command: if x then y. This is a programmed demon; when  situation
x is true, we must do y. (vi) Delete all mention of x. This is like a
replace, but we go through  the  assert  lists  with  an  eye  toward
deleting  unnecessary  worries. (vii) Infinite loop in x from y to z.
If we can't justify this, we insert a test to break out of the  loop.
Justification might be that this loop is in the top-level function of
the  system,   where   we   never   wnat   to   break   out.   (viii)
Incomprehensible:  x, y. (there is a "bug" in x manifesting itself as
y) Never needed to write CF, so  not  implemented.  Should  call  FIX
INCORRECT  PIECE  (which  is  also  not  in  yet) or ask the user for
assistance.

⊗4GET NEW INFORMATION⊗*. Naturally, it is not thrilled if (-68) there
exists  some  new but unexamined information, and it is happy (50) if
there is none. The prerequisites ensure that the  user  is  aware  of
what  PUP6  wants,  and  if the theorem prover can't deliver it, PUP6
asks the user for some. If PUP6  asks  for  something  general  ("any
task")  it  is because it knows precisely that this is what it wants,
not out of ignorance! During execution, the specificity  check  demon
is  active;  he  ensures that it is indeed phrased as specifically as
possible; if not, MAKE SPECIFIC  will  be  called.  This  is  a  very
uncomplicated  BEING, and a very unpopular one to use since we should
squeeze every drop of meaning out of what we have before  asking  for
more information.

⊗4EXTRACT RELEVANT SUBSET⊗*. This likes (70) there to be a great deal
(⊗7≥⊗*50 pieces) of new information, and dislikes (-80) it if  there  are
under a dozen such tokens. It finds and evaluates knowledge variables
to constrain what should be looked at currently. This is never called
in the dialog, though it was in the protocol.

⊗4ANALYZE  IMPLICATIONS⊗*. The WHEN part is unhappy (-60) if there is
usable information already, since this BEING  is  fairly  costly.  It
also examines the size of the new info list to see just how long this
search will be. The BEING locates the code  that  will  be  affected,
predicts  the  affects, and sees how desirable this is. This BEING is
also never needed to write CF.

⊗4MAKE ENCODABLE⊗*. If all else fails, this BEING tries  replacing  a
function  by  one of its alternatives or, as a last resort, by one of
its generalizations.  This last resort is never needed to write CF.

⊗4ENCODE⊗*. Despite its key name, this BEING is mostly a  bookkeeper!
It  runs  around the assert lists, gathering up enough information to
encode a specified little piece of code. A program  schema  is  built
up,  instantiated  as  much  as possible, printed out for the user to
refer to, and passed  to  a  highly  optimized  recursive  auxilliary
function,   GETCODE.   Some   worrying   about   the   arguments   is
done,including what they might be instantiated as. We inform the user
of  the code BEING written, and a prerequisite causes the function to
become made into a BEING.

⊗4STUDY TYPE⊗*. This BEING  accepts  a  BEING  call,  looks  at  that
BEING's  SPECIALIZATIONS part, translates each entry into a decision,
and dumps these onto the undeferred decision list. A  deferral  demon
promptly attends to them.

⊗4GET  DATA  STRUCTURE⊗*.  We call select-structure type, and use its
advice to point to the proper knowledge variable. We eval it  to  set
up  the various parts of the data structure. In unclear cases, we may
ask the user whether the argument really  is  a  data  structure.  We
ensure  that this object is a BEING (else we make it one,) and we add
warnings to the effect that there might  not  be  any  insertions  or
deletions;  we'll  worry  about that much later, by another BEING. We
know that the elements of a data  structure  are  themselves  usually
data  structures,  so  one the prerequisites says that we must try to
make the arguments into data structures as well.

⊗4GETCODE⊗*. This is a long,  special-case,  recursive  function.  It
goes  through  a  piece  of code with two jobs: to build up a list of
arguments to this function, and to get names for  specific  instances
of  general  BEINGs.  Part of the kludgy character is due to the fact
that there are non-BEINGs in the code:  primitive  forms  (structure,
tuple,  vector,  class,  comment,  atoms), primitive functions (read,
null, and, ...), primitive variables (T, NIL, 4,  ...).   By  keeping
closely  to  the  theoretical  ideals  implicit  in  the  ideas, this
function would probably become trivial.

⊗4GET NAME⊗*. First we study plausible names for the new  specialized
BEING.  We  make  the  user  aware of them. We examine the BEING name
carefully, to see if it was just mentioned in the same piece of  code
(probably  then  the same name), whether it's ever been mentioned and
specialized, and so on. Sometimes we end up deciding not to get a new
name,  sometimes  we  pick  one  and just tell the user, sometimes we
recommend some old specialized name. In 90% of the cases, though,  we
simply say "give me a name for ...". A new-name counter is maintained
to ensure unique names, and this number is appended onto the  end  of
what  the user types, unless it's an already-existing BEING name. The
user my type ] (and usually does), indicating that PUP6 is to choose.
PUP6 always informs the user what the name is at the end.

⊗4MAKE  NEW  BEING⊗*.  This  BEING  has the awesome responsibility of
giving life to new BEINGs. As is the case with neurons, soldiers, and
all  (good) BEINGs, no one BEING really does much when you look at it
in isolation. Thus this one already gets the name of the  BEING,  the
name  of  its  parent  (its  least  general  generalization), how the
metacodes of these two differ, the argument list, the reason for this
specialized  BEING  to  exist,  what  extra qualities it possesses or
lacks wrt its parent, etc.  It can  figure  out  who  it  affects  by
examing its various parts, and it bases the complexity vector on that
of the parent and on the changes in this new BEING. Thus it basically
does  gets,  evals,  and  puts.  It updates various assert lists, and
semi- compiles the new BEING. One bit  of  knowledge  says  that  the
explicit  args check may be significantly different, and the user may
be queried.

⊗4SEMI  COMPILE⊗*.  Basically,  BEINGs  only   lend   themselves   to
interpreting;  to  help  speed  up  this process, this BEING can take
advantage of regularities and simplicities in another BEING's  parts,
and  turn  out a fast function to do an equivalent job.  For example,
if a BEING doesn't enable any new demons, we needn't push  the  demon
stack at the beginning and pop it at the end.


	⊗5E.  Low-level  problem-independent   knowledge:   bits   of
programs⊗*

⊗4PROPOSE  PLAUSIBLE  NAMES⊗*.  This  BEING is called by GetName, and
should incorporate a good model of user psychology of  name-choosing.
Currently, it applies Initials, Mainwords, Firstfew, and compositions
of these, to the task description sentence.

⊗4SELECT  STRUCTURE  TYPE⊗*.  This  is  a  true  bit  of  programming
knowledge: if the structure is composed of several weakly-interacting
pieces tied together through association with one atom, then the data
structure should be a  list  of  these  atoms,  with  the  associated
structures  BEING stored on the property lists of the atoms. If there
are only a couple pieces, or they interact strongly, we should use  a
nested list structure instead.

⊗4ELEMENT⊗*. All we know about an element is that it is a member of a
data structure, and that we should not be ashamed to ask the user  to
clarify  himself  if  he mentions this. The ConceptFormation BEING --
not the ELEMENT BEING  --  should  note  that  future  references  to
ELEMENT actually refer to a scene, an instance of a concept, and that
references to class refer to the model of a concept, a set of scenes.
This may change as new data structures come into existence.

⊗4MODIFY  STRUCTURE⊗*. Generally, we will be given a typical element,
and must identify the structures it belongs to, and modify them.  The
precise  details  indicate that some subset of CONDITIONAL INSERTION,
CONDITIONAL DELETION, and COMPLEX ALTERATION will be involved.

⊗4GET HOLD OF⊗* by guessing and checking. We must discover whether an
algorithm  already  exists which can get arg1. If not, we try to find
one which can get arg1 and  some  other  effects.  We  structure  the
function  as some of COMPUTE, GENERATE&TEST, and SEARCH.  Finally, we
must decide  now  on  the  type  of  error  recovery  desired:  none,
backtrack, or correct-and-try-to-proceed.

⊗4TAKE  HOLD  OF⊗*  trivially. We examine the flow of control through
the preceding code, to decide whether arg1 has ever been SET. If  so,
we  must  ask  the  user whether or not to read in a new value. If no
read is to be done, then this BEING reduces to a  simple  assignment,
or  perhaps  to nothing at all. Otherwise, we read in the object, and
assign its various subparts to SOME PART OF it.

⊗4IS OF TYPE⊗*. This BEING is a predicate which is too low-level  and
general  to  do much. Basically, it helps formulate a question to the
user, who must explain to PUP6 how  to  construct  any  predicate  it
comes  across,  usually just by translating a sentence the user types
in.

⊗4COMPLEX  ALTERATION⊗*.  This  BEING  is  always  replaced  by  some
initializing  assignments,  followed by calls on MODIFY STRUCTURE for
some  subparts  of  arg1.  A  bit  of  advice  is  that  if  arg1  is
unstructured,  try to get it structured. If this fails, maybe what is
really wanted is to modify the structure of which arg1 is a member.

⊗4CONDITIONAL DELETION⊗*. As above, we look  at  the  structuring  of
various  arguments  to  decide  what is really supposed to be deleted
from where. We check with the user, remind him  of  various  bindings
relevant  to the current call, and ask him to describe (1) under what
conditions we do the deletion, (2) what exactly do we  delete.  These
are  translated,  analyzed  in  the  context  of  deletion,  and help
determine the deletion piece of code.

⊗4CONDITIONAL INSERTION⊗*. This is similar to  the  preceding  BEING.
Here  we  also worry about whether the entity to be inserted has ever
been bound. If not, we must see that it is! Often, this binding  will
be  related  to the Initialize piece of the DataStructure part of the
BEING representing the structure we're inserting  into.   Since  some
data  structures  have  several similar but distinctly-named elements
existing simultaneously, we have lots of  little  worries.  After  we
have  planned out the code, we check with the coding warning list and
add to it; e.g., any undefined initial value of a variable in a piece
of  code  we  stuck  in  here, will also be uninitialized here. If we
later decide never to worry about the first initialization,  we  must
not forget this one! This is a frequent source of bugs, I think.

⊗4GENERATE&TEST⊗* and ⊗4COMPUTE⊗* are not needed or implemented.

⊗4SEARCH⊗*.  Currently,  a  primitive  type of searching suffices. We
simply execute the iteration FOREACH X IN XSET DO (TEST X).  If we're
unsure,  we  check  that  XSET  has  the  form SET OF (PLURAL X). The
specializations tell us to  worry  about  termination  conditions.  I
suppose this BEING could also be used for generate-and-test.

⊗4FOREACH⊗*.  Not surprisingly, this is the iteration BEING. It is an
NLAMBDA function, so its arguments aren't surrounded by quotes. There
are  various  minor decisions to make, which simplify any specialized
version: there may or may not be an "until" condition; we must get it
and also decide what to bind the iteration variable to and what value
to return, both in case this condition is met, and in case we exhaust
the  space. Often, we will decide to leave some of these unspecified,
put notes about them on the coding warning list, and not worry  about
them for a long time.

⊗4TEST⊗*.  This  BEING  is  a  predicate  which  is oriented toward a
threshold of acceptability, whereas  IS_OF_TYPE  is  oriented  toward
separating  cases.  It  either  has  the  flavor  of comparing, or of
competition.  We must also decide  whether  the  result  is  nominal,
ordinal,  or  of ratio caliber. These latter two never crop up, which
is why we assume the test is a predicate always.

⊗4SOME PART OF⊗*. We either get this simple destructive  function  by
examples  (like  Shaw's  program)  or  by translating a user-supplied
English  sentence  describing   what   it   does.   Typically,   some
combinations  of CAR and CDR, occasionally uses some constants (1, T,
NIL) or constructive primitives (CONS, NCONC).

⊗4COMPARE⊗*. We must worry  about  whether  the  result  is  nominal,
ordinal, or ratio. We also decide whether the comparison is a JOINING
FUNCTION applied to its arguments, a constant function (executed only
for  side  effects),  or a JOINING FUNCTION applied to the results of
COMPAREing corresponding subparts of the arguments. This last case is
both  frequent  and  complicated.  If neither argument is structured,
this is impossible. If both are highly structured,  their  structures
must  have a nontrivial amount of correspondence in order to succeed.
If only one argument is structured, this strongly  suggest  that  the
other  one  should  be  similarly  structured.  Often we go ahead and
structure it without asking the user (inference by analogy.)

⊗4BETTER⊗*. We've discussed this earlier. Here we  should  note  that
when  called  on  to  write  a  new,  specialized BETTER function, it
chooses either a simple function (T, NIL) to  allow  an  optimization
(replace  by  CONS,  replace  by  NCONC1),  or  it  chooses a complex
comparing function (e.g., alphorder, write-program itself!).

⊗4JOINING FUNCTION⊗*. This is a way  of  condensing  results.  It  is
typically  a known function, such as AND, OR, PLUS, MAXIMUM, PROGN...
which is determined by (i) the character of  the  result  (numerical,
T/F)  and  (ii)  whether  we  are in a DO UNTIL loop, a DO REPEATEDLY
loop, or neither of these loops.


	⊗5F. Programming Knowledge stored in variables⊗*

	To  resolve  an  ADAPTATION  decision: Ask for sample dialog,
symbolically run current code, modifying I/O formats.

	To defer any decision whose AFFECTS part  is  known:  It  may
translate as some detail of x; in that case, wait until some code for
x already exists. The affects part may translate as The x  algorithm;
in this case we worry as soon as PUP6 begins DO-ing any coding at all
of x.

	To defer an ALTERNATIVES decision: Examine the  coding  tasks
in  all  cases,  and  try to find some common head and/or some common
tail. If there is any, try to defer the decision until after  writing
code  for  this  common  subtask sequence. If one alternative exactly
matches the common sequence,  we  can  temporarily  assert  that  the
decision has been made to do this simplest BEING.

	To  terminate an AND loop: The conjunction is usually between
highly similar objects. Related to how to parse a sentence containing
ANDs.

	To resolve a BOOLEAN decision: Ask the user to respond Yes or
No. The decision has special Yes, No, and Both parts; in  each  case,
two of them will be evalled.

	To  resolve a DEFINITION decision: Locate the defined object,
reaffirm that it is undefined, ask  the  user  to  define  it,  check
whether  it  is  a predicate, data structure, etc., and tell the user
about such constraints.

	To resolve a DICHOTOMY decision: Each such decision  contains
a  little  program  which now is evaluated. If it succeeds, its value
answers the decision; if it fails, we have to ask the user to  choose
alternative 1 or 2. The choice points to a little program to run, and
its value is the desired resolution.

	To resolve a PREDICATE  decision:  Fix  the  context  of  the
predicate  call,  try  to  relate this predicate to some known tests,
and, if this fails, ask the user. His response is specially processed
in the context of a predicate fixation.

	To  set  up  a data structure stored as a LIST STRUCTURE: The
initialization is a simple SETQ to an as-yet-undefined value.  Access
is  simply by mentioning the name. Insertion is by Merge-in or Merge.
Deletion is by Pullout or Setdifference.

	To set  up  a  data  structure  stored  as  a  PROPERTY  LIST
STRUCTURE:  Delineate the pieces to be associated with each atom, and
name them. Accession is via GETP. Insertion s  via  a  GETP,  then  a
MERGE-IN,  then a PUT. Deletion is via a GETP, then a PULLOUT, then a
PUT. Initialization is a PUT of a SETQ to an as-yet undefined  value.
Each   named  substructure  must  itself  become  a  data  structure,
typically a simple list structure.

	To resolve a SOMEOF decision: The user must  be  sufficiently
informed  about the choices. He types back a non-null, ordered subset
of those choices. We examine them to see if they should  be  enclosed
in  a  PROGN  or  in  a  REPEATEDLY, and whether we would like to see
something structured in a certain way.

	To resolve a SUBSETOF decision:  Similar  to  above,  but  no
fancy investigation, just string the choices together in a PROGN.

	To  defer  any  decision  whose  WHEN  part  is  provided: We
transform "before deciding firmly how to ←x ←←y" into something  like
"member (cons detail-of-$x-ing $y) doing-pup-list". We also translate
Before  any  ←←x  routine  is  finalized,  After  ←←x  routines   are
finalized, and similar phrases. These must always evaluate T or NIL.


	⊗5G. Demons and functions of interest⊗*

LIST-JOIN, MERGE-IN, PULLOUT. These  rather  standard  functions  are
given a tiny bit of advice: if their "element" is more like a sublist
than an element of their "list", then they assume that what was meant
was append or merge or setdifference, not cons or insert or remove.

LONG NAME DEMON. If any name becomes unwieldy, he notices it and asks
the user for a nickname.

PERMIT  DETAILED  DECISION.  Implicit  near  the  beginning  of  each
decision,  PUP6  called  this  function. It asks the user if he wants
more details, and if so it gets them and prints them out.

STRUCTURE INDUCING DEMON. If the object is a BEING  already,  special
considerations   apply.   If  the  object  and  all  arg  values  are
ill-defined, we decide not  to  do  any  structuring.  Otherwise,  we
investigate  the  effects  of  structuring the object into the pieces
specified in the args. If there  is  no  problem,  and  if  the  user
consents,  we  tack  the appropriate Replace messages onto the coding
warning list (with a high priority). We activate Long Name Demon.

⊗5Natural Language  Translation⊗*.  We  have  already  discussed  the
TRANSLATE BEING and the basic way of handling natural language input.
Several BEINGs exist  primarily  for  this  purpose;  RECOGNIZE-ARGS,
RECOGNIZE-C*R,      RECOGNIZE-CONDITIONAL,     RECOGNIZE-CONJUNCTION,
RECOGNIZE-EQUALITY, RECOGNIZE-FUNCTION-RETURNS,  RECOGNIZE-INCLUSION,
RECOGNIZE-LITERALS,     RECOGNIZE-NUMBER,    RECOGNIZE-SET-RELATIONS,
RECOGNIZE-SOME-MEMBER, ADD-DEFINITION, ADJECTIVE-HANDLER, REPEATEDLY.
Also,  there  are  several  functions  related  to translation: e.g.,
UNGERUNDIFY, PLURAL, OPPOSITE. All these  are  straight-forward,  and
their task is obvious from their name.

.SELECT 1

.SSEC(The increment of knowledge necessary to write GI)

⊗4APPLY RULE⊗*.  This BEING accepts  two  arguments,  which  must  be
interpretable  as  a string and a rule, respectively.   The string is
compared against the left side of the rule and,  if  applicable,  the
change  indicated by the right side is executed on the string.  It is
immediately encodable if the user wishes all possible applications of
the  rule  to  the  string;  else  a more specialized version must be
synthesized.

⊗4CONSTRAIN⊗*.  Try first to decide if it is meaningful for the given
structure  to  be constrained, and, if so, how.  Next see whether any
other BEINGs can  help.    Finally,  ask  the  user  to  specify  any
constraints  he can think of.  For example, can a list structure grow
indefinitely, or can we use some fancy programming trick because  the
size stays small?

⊗4GRAMMATICAL  INFERENCE⊗*.  Needless  to  say, this is a high-level,
domain-specific BEING! It must infer grammars from exemplary strings;
it  knows  this to be the only reasonable g.i. paradigm. If it fails,
some   genralizations   are   inductive    inference,    enumeration,
problem-solving;   some   alternatives   are  concept  formation  and
simulated evolution.  There are many minor decisions, similar to  the
concept  formation decisions (e.g., examine a sample GI-user dialogue
to finalize the printing formats). The major decision is dichotomous:
whether  our new specialized BEING should retain the ability to input
the type of grammar and vary its  strategy  accordingly,  or  whether
only  one  fixed  type of grammar (e.g., context-free) will always be
used, and may be "built in" to the code. The result of this  decision
is to pass control to one or the other of the following two BEINGS.

⊗4INFER  MULTI-CLASS  GRAMMARS⊗*. We read in the type of grammar, and
then call the appropriate specialist for that type.  Thus we  have  a
big switch here.

⊗4INFER   FIXED-CLASS   GRAMMARS⊗*.     This  routine  determines  at
program-synthesis time what the class is going to be, and  thus  will
be  a  fixed  call to one of the following four BEINGS.  The speedups
will arise from using the constraints on the rules.

⊗4INFER PHRASE-STRUCTURE GRAMMARS⊗*. There are no rule constraints in
a  type  0  grammar;  each half of the rule is viewed as an arbitrary
list   of   letters.        When   a   TEST   is    indicated,    the
fringe-of-consciousness demon must report it is thinking of PARSE. The
left and right sides of a rule will be destructive operations on  the
data representation of a rule.

⊗4INFER  CONTEXT-SENSITIVE  GRAMMARS⊗*.  We  shall only report on the
differences between the INFER...  BEINGS.  This one  knows  that  the
right  side  of  the  rule must be at least as long as the left side.
This will be used as a pruning  heuristic  when  proposing  plausible
rules.

⊗4INFER  CONTEXT-FREE  GRAMMARS⊗*.  Grammars  of type 2 have as their
left side a single nonterminal. Further simplifications can occur  by
only  working  toward  a  Griebach Normal Form or Chomsky Normal Form
grammar, although from the standpoint of inference energy  these  are
harder.

⊗4INFER  REGULAR  GRAMMARS⊗*.  A type three grammar has a unit on the
left and a  pair  of  them  for  a  right  side  (one  terminal,  one
nonterminal). This is a very powerful pruning heuristic.

⊗4MAJOR  MODIFY  STRUCTURE⊗*.   The old, simple "insert,delete,alter"
paradigm of modification was no longer sufficient. This BEING heads a
whole  complex  of  modify  BEINGS,  including  the  old  one  as the
low-level workhorse primitive. Here is a sketch of the organization:
.BEGIN NOFILL GROUP SELECT 8
		Major-Modify-Structure
		    /     ~     \   
            Modify-Until  ~  Modify-Some
		    \	  ↓     / 	
        The-Original-Modify-Structure-BEING
.END
So  this  top-level  modifier  calls  some  subset of the three lower
modification BEINGS. Later, we  had  to  add  a  fourth  alternative,
EXAMINE DATA STRUCTURE, to aid in writing the  PL program.

⊗4MODIFY  SOME⊗*. We determine a set S and a predicate P at synthesis
time.  At run time, we map  through  S  and  apply  P;  all  elements
responding   positively  are  modified  (using  the  original  MODIFY
STRUCTURE.) The decisions about P and S are easily deferrable.

⊗4MODIFY  UNTIL⊗*.    This  BEING  is  simply  an  order  to  compose
REPEATEDLY  π. MODIFY_STRUCTURE.  The former BEING bears the brunt of
the responsibility of the interface.

⊗4PARSE⊗*. Attempt to parse a string from the current set  of  rules,
by  reversing  each rule and composing their applications.  We decide
at synthesis time whehter or not to maintain a parse tree, whether or
not to maintain a list of the rules used during the parse, whether we
stop parsing at any legal string or only at  "S,"  whether  we  parse
forwards  or backwards or both, how deeply in each direction (this is
always deferred  until  much  later),  whether  one  direction  after
another  or (simulated) simultaneously. We look for the DataStructure
part of the BEING representing a rule, and ask him about  constraints
on  the  rule,  and  about  how to destructively recover the left and
right sides separately.

⊗4PARSE BACKWARD⊗*.  This BEING is given two strings  and  a  set  of
rules;  the task is to apply anti-rules to the target string until it
becomes the initial string.  This is  typically  done  breadth-first.
Special  modifications  must  be  made  if  there  is a parse tree to
maintain, if a set of rules used must be maintained, etc.  The  basic
body  is a nest of FOREACH calls (∀rule, ∀way of applying the rule to
the string, recurse). To avoid infinite recursion, we must  supply  a
third argument: the depth to which we compose these anti-rules before
we give up.  When calling itself  recursively,  this  level  will  be
decremented.

⊗4PARSE FORWARD⊗*. This BEING is analogous to the previous one, using
rules themselves instead of anti-rules. Notice how clearly the  place
to  insert  searching  heuristics is marked out for us (although none
are present.)

⊗4STRING⊗*.  This is a structure whose parts are a name,  a  list  of
letters,  a  set of comments.  It is advisable to use list structures
rather than property lists to  represent  strings,  since  they  will
probably  only  be  accessed by one of their three parts.   In the GI
program,  we  don't  use  STRING  itself,  but  rather   we   mention
UNCOMMENTED   STRING,  which  causes  this  BEING  to  create  a  new
specialized version of itself, sans the third, comments part.

.SSEC(The increment of knowledge necessary to write  PL)

⊗4EXAMINE  STRUCTURE⊗*.  This  is another one of the parts of a major
MODIFY structure.  If the fringe of consciousness demon can't come  up
with  a reasonable matching function, one is selected now.  The basic
body says to do PATTERN MATCH, using this match function, and  convey
the  results to the caller (who may be the user.) The inputs are thus
a pattern, a data structure name, and possibly  a  hint  to  a  match
function.

⊗4PATTERN MATCH⊗*. This existed as a system function earlier, but for
 PL it  is  necessary  to  write  a  tailored  pattern-matcher.    In
particular,   PL  demands that we strip away the common head and tail
from both pattern and expression, and then compose the two  remaining
pieces  into  the  left  and right sides of a new plausible rule, and
then check that this conforms with the constraints on rules. This  is
certainly different from the type of match needed by CF!  Notice that
we had to add the "eliminate common head/tail" functions to our  list
of system primitive functions.

.SELECT 6
.EVERY HEADING(⊗7{DATE}     D.  Lenat,,page {PAGE}⊗*)
.PAGE FRAME 55 HIGH 89 WIDE
.TITLE AREA HEADING LINE 1
.AREA TEXT LINES 2 TO 55
.PAGE←PAGE-1
.BEGIN SPACING 10 MILLS
.ASEC(Appendix 3: BEING usage data)

	To communicate the degree of heterarchy actually utilized by PUP6, we 
present usage data about all the BEINGS.  For each one, we give: its length (in 
cells), the number of parts which were actually coded,
the number which were
accessed in each of the
three experimental dialogues (3 numbers, one for each 
dialogue), the total number of times each
BEING was in control (3 numbers), the total time spent while this
BEING was in control (not
including time spent in a BEING called by this one hierarchically; 3 numbers).
To avoid giving the reader a false impression of the degree of intelligent
inter-BEING communication, we have eliminated from the table below all the
thousands of references which are made during translation (when ⊗4every⊗*
BEING is asked "do you recognize ...?") and during goal statements (when
⊗4every⊗* BEING is asked "can you bring about ...?").
Likewise, it is more descriptive to view the size of a BEING in terms of the
number of list cells it occupies (⊗2LENGTH⊗* column below), 
rather than the number of lines it needs
when pretty-printing.

.SELECT 6
.TABS 30,35,40,45,50,55,60,65,70,77,84
.TURN ON "/" FOR "\"
.NOFILL
.PREFACE 10 MILLS
.EVERY HEADING(,,)

⊗2BEING NAME	          LENGTH PARTS  A C C E S S E D/C O N T R O L    /  C P U - T I M E
///CF/GI/PL/CF/GI/PL/CF/GI/PL⊗*
ADAPT-PRECONCEIVED-FUNCTION/28/5/348/304/120/0/0/0/0.0/0.0/0.0
ADD-DEFINITION/191/11/3/5/1/3/5/1/11.2/12.0/1.2
ADJECTIVE-HANDLER/245/14/0/0/0/1/1/0/0.2/0.2/0.0
ANALYZE-IMPLICATIONS/276/14/57/35/25/0/0/1/0.0/0.0/10.1
APPLYRULE/118/10/0/55/0/0/0/0/0.0/0.0/0.0
ASK-USER-ABOUT/195/12/98/0/0/50/48/11/821.4/593.3/40.1
BETTER/405/13/121/0/53/438/396/164/105.2/75.4/20.2
CHOOSE-FROM/312/11/0/0/0/91/83/35/25.5/19.3/5.2
CLARIFY-IMPROBABLE-SITUATION/2102/13/694/588/286/29/26/17/582.5/102.4/24.7
Classificatory-Concept-Formation/37/6/3/0/0/0/0/0/0.0/0.0/0.0
COMPARE/982/12/213/0/0/0/0/0/0.0/0.0/0.0
COMPARITIVE-CONCEPT-FORMATION/45/6/3/0/0/0/0/0/0.0/0.0/0.0
COMPLEX-ALTERATION/498/10/142/0/0/0/0/0/0.0/0.0/0.0
COMPLEX-COMPARE-FN/102/5/55/0/0/0/0/0/0.0/0.0/0.0
COMPLEX-MODIFY-STRUCTURE/430/9/0/61/0/0/0/0/0.0/0.0/0.0
CONCEPT-FORMATION/582/18/52/0/0/0/0/0/0.0/0.0/0.0
CONDITIONAL-DELETION/878/12/144/96/50/0/0/0/0.0/0.0/0.0
CONDITIONAL-INSERTION/1244/11/283/112/47/0/0/0/0.0/0.0/0.0
CONSTRAIN/223/14/0/0/0/2/1/0/0.6/0.7/0.0
DATA-STRUCTURE-DELETIONS/756/12/0/0/0/2/0/2/0.4/0.0/0.2
DATA-STRUCTURE-INSERTIONS/756/12/0/0/0/2/0/2/0.3/0.0/0.2
DEFER-DECISION/289/15/0/0/0/167/91/17/6.9/26.8/1.2
ELEMENT/59/8/76/106/0/0/0/0/0.0/0.0/0.0
ENCODE/1018/12/0/0/0/49/40/11/776.3/531.8/76.7
EXAMINE-STRUCTURE/146/11/0/0/52/0/0/0/0.0/0.0/0.0
EXTRACT-RELEVANT-SUBSET/203/13/32/28/20/0/0/0/0.0/0.0/0.0
FAST-GET-NAME/632/16/0/0/0/3/2/1/1.7/0.7/0.4
FAST-SATISFY/385/18/0/0/0/0/0/0/0.0/0.0/0.0
FILL-IN-UNDEFINED-SECTION/463/14/977/809/260/49/40/11/160.2/121.6/14.2
FIX-INCORRECT-PIECE/21/4/348/304/120/0/0/0/0.0/0.0/0.0
FOREACH/938/12/51/62/0/0/0/0/0.0/0.0/0.0
GET-DATA-STRUCTURE/780/13/17/0/48/15/0/2/12.7/0.0/5.2
GET-HOLD-OF/301/11/59/59/0/0/0/0/0.0/0.0/0.0
GET-NAME/592/14/0/0/0/65/52/19/68.0/142.0/6.2
GET-NEW-INFORMATION/192/15/60/43/41/2/1/2/0.2/<0.1/0.2
GRAMMATICAL-INFERENCE/219/12/0/46/0/0/0/0/0.0/0.0/0.0
Infer-ContextFree-Grammars/148/13/0/0/0/0/0/0/0.0/0.0/0.0
Infer-ContextSensitive-Grammars/147/13/0/0/0/0/0/0/0.0/0.0/0.0
Infer-FixedClass-Grammars/131/10/0/46/0/0/0/0/0.0/0.0/0.0
Infer-MultiClass-Grammars/88/10/0/0/0/0/0/0/0.0/0.0/0.0
Infer-PhraseStructure-Grammars/143/14/0/55/0/0/0/0/0.0/0.0/0.0
Infer-Regular-Grammars/155/13/0/0/0/0/0/0/0.0/0.0/0.0
IS-OF-TYPE/143/11/108/214/51/0/0/0/0.0/0.0/0.0
.SKIP TO COLUMN 1
⊗2BEING NAME	          LENGTH PARTS  A C C E S S E D/C O N T R O L    /  C P U - T I M E
///CF/GI/PL/CF/GI/PL/CF/GI/PL⊗*
JOINING-FUNCTION/223/13/49/0/0/0/0/0/0.0/0.0/0.0
LIST-STRUCTURE/65/10/273/0/480/0/0/0/0.0/0.0/0.0
MAJOR-MODIFY-STRUCTURE/35/6/12/126/48/0/0/0/0.0/0.0/0.0
MAKE-A-GUESS/207/10/0/0/0/0/0/0/0.0/0.0/0.0
MAKE-ENCODABLE/162/11/0/0/0/66/52/16/20.9/54.1/1.2
MAKE-NEW-BEING/461/11/0/0/0/56/37/23/299.5/204.5/86.7
MESSAGE/236/15/0/0/0/46/37/26/24.0/7.8/4.2
METRICAL-CONCEPT-FORMATION/22/4/3/0/0/0/0/0/0.0/0.0/0.0
MODIFY-SOME/263/9/0/45/0/0/0/0/0.0/0.0/0.0
MODIFY-STRUCTURE/158/12/676/366/54/0/0/0/0.0/0.0/0.0
MODIFY-UNTIL/116/9/0/45/0/0/0/0/0.0/0.0/0.0
OBTAIN-USABLE-INFORMATION/199/13/943/808/342/7/7/5/0.5/0.6/0.2
OPTIMIZE/21/4/0/0/0/1/1/1/(0.0)/(0.0)/(0.0)
PARSE/1223/12/0/73/0/0/0/0/0.0/0.0/0.0
PARSE-BACKWARD/492/11/0/55/0/0/0/0/0.0/0.0/0.0
PARSE-FORWARD/488/11/0/51/0/0/0/0/0.0/0.0/0.0
Partition-a-Domain/286/16/55/53/0/0/0/0/0.0/0.0/0.0
Partition-by-Take-Class-Get-Ele/40/7/0/0/0/0/0/0/0.0/0.0/0.0
Partition-by-Take-Ele-and-Class/64/9/4/4/0/0/0/0/0.0/0.0/0.0
Partition-by-Take-Ele-Get-Class/67/9/4/4/0/0/0/0/0.0/0.0/0.0
PATTERN-MATCH/435/12/0/48/0/0/0/0/0.0/0.0/0.0
PROBABILITY=0:#/122/10/4/0/0/0/0/0/0.0/0.0/0.0
PROBABILITY=1:#/106/10/4/0/0/0/0/0/0.0/0.0/0.0
PROBABILITY>0&<1:#/118/10/4/0/0/0/0/0/0.0/0.0/0.0
PROPOSE-PLAUSIBLE-NAMES/356/15/0/0/0/3/2/1/1.4/1.0/0.9
RECOGNIZE:#/226/11/48/0/0/0/0/0/0.0/0.0/0.0
RECOGNIZE-ARGS/52/5/0/0/0/0/0/0/0.0/0.0/0.0
RECOGNIZE-CAR/127/4/0/0/0/0/0/0/0.0/0.0/0.0
RECOGNIZE-CONDITIONAL/66/3/0/0/0/0/0/0/0.0/0.0/0.0
RECOGNIZE-CONJUNCTION/139/3/0/0/0/0/0/0/0.0/0.0/0.0
RECOGNIZE-EQUALITY/130/4/0/0/0/0/0/0/0.0/0.0/0.0
RECOGNIZE-FUNCTION-RETURNS/127/4/0/0/0/0/0/0/0.0/0.0/0.0
RECOGNIZE-INCLUSION/100/4/0/0/0/0/0/0/0.0/0.0/0.0
RECOGNIZE-LITERALS/191/5/0/0/0/0/0/0/0.0/0.0/0.0
RECOGNIZE-NUMBER/84/3/0/0/0/0/0/0/0.0/0.0/0.0
RECOGNIZE-SET-RELATIONS/131/3/0/0/0/0/0/0/0.0/0.0/0.0
RECOGNIZE-SOME-MEMBER/148/3/0/0/0/0/0/0/0.0/0.0/0.0
RECOGNIZE-TAIL/47/3/0/0/0/0/0/0/0.0/0.0/0.0
REINVESTIGATE-DECISION/200/13/0/0/0/10/21/3/0.3/0.6/0.1
REPEATEDLY/196/11/1/2/1/0/0/0/0.0/0.0/0.0
RESOLVE-DECISION/184/13/0/0/0/50/48/11/2.5/2.4/0.4
SATISFY/311/18/0/0/0/329/235/101/249.2/171.2/71.6
SCENE/48/6/37/0/0/0/0/0/0.0/0.0/0.0
SEARCH/375/13/4/4/0/0/0/0/0.0/0.0/0.0
SERVE/204/15/0/0/0/1/1/2/0.3/0.1/0.3
SIMPLE-COMPARE-FN/127/11/48/0/47/0/0/0/0.0/0.0/0.0
SOME-PART-OF/220/11/351/196/0/0/0/0/0.0/0.0/0.0
STRING/98/12/0/49/0/0/0/0/0.0/0.0/0.0
STUDY-TYPE/224/11/0/0/0/71/51/14/30.1/18.5/1.4
SUPPORT&DUMP/445/11/0/0/0/1/1/1/19.0/16.7/12.3
TAKE-HOLD-OF/505/10/110/174/46/0/0/0/0.0/0.0/0.0
TEST/269/8/48/0/0/0/0/0/0.0/0.0/0.0
TRANSLATE/328/17/73/82/47/111/33/22/196.4/31.0/16.1
USE-INFORMATION/148/11/399/389/137/3/5/1/0.5/0.7/0.1
UTILIZE/328/12/0/0/0/81/64/14/56.2/60.8/8.4
WHEN-NEXT/244/12/0/0/0/81/64/14/26.3/36.9/2.0
WRITE-PROGRAM/631/17/0/0/0/1/1/1/32.7/12.3/2.5
.END
.FILL
.SELECT 1
.TURN OFF "/"
.TURN ON "\" FOR "%"
.EVERY HEADING(⊗7{DATE}     D.  Lenat,BEINGs......  {SECTION},page {PAGE}⊗*)
.PAGE FRAME 54 HIGH 89 WIDE
.AREA TEXT LINES 4 TO 53
.TITLE AREA HEADING LINES 1 TO 3
.TITLE AREA FOOTING LINE 54
.PAGE←PAGE-1
.ASEC(Appendix 4:   Synthesized parts of CF program)

This  appendix  opens  a  detailed  example  of  PUP6  in  operation.
Fragments of the target concept formation program are exhibited,  and
on  page  A4.7  is  a  flowchart  for a hand-coded version of CF, the
target concept formation program discussed earlier.  Like PUP6,  both
hand-coded  and  synthesized  versions of CF are written in INTERLISP
[Teitelman, 197?] with slight  additions  (setdifference,  disk-dump,
etc.)   only.        Following   each   hand-coded  piece  comes  the
corresponding  BEING  version  created  by  PUP6.     Some  functions
mentioned  are  system  functions used to augment the language (e.g.,
MATCH.) A few functions have  been  omitted  to  aid  in  readability
(e.g.,  VECTOR  and  TUPLE,  which  are  inverse  quote  forms of the
function LIST). The reader should examine the META-CODE  sections  of
each  BEING;  they  contain  much of the  \4executable\* code of the BEING.
The  choice  of  functions,  while  not  a  random  sample,  is   not
intentionally biassed. The opening, top-level functions are shown (by
hand and by PUP6), and then a  very  low-level  maintenance  function
(delete a feature from the NO relations of a model) is exhibited.

The next phase of the extended CF example is  found  in  Appendix  5.
There is a transcript of the dialogue between the user and PUP6 which
produced this synthesized code. User responses are italicized to ease
the  reading.     Notice  how the user may interrupt and ask PUP6 for
clarification.

The sixth appendix section presents a session with  this  synthesized
program  itself  running. During the exectution of CF, the user stops
and occasionally asks it questions; the answers are at about the same
level as those one gets from PUP6 itself during the dialogue.

.BEGIN SELECT 7 NOFILL PREFACE 10 MILLS



\4The top-level functions do initialization and repeatedly build up models:\*

(CF
  [LAMBDA NIL
    (INITIALIZE-1)
    (PARTITION-A-DOMAIN])

(INITIALIZE-1
  [LAMBDA NIL
    (SETQ YES-RELATIONS (QUOTE YES-RELATIONS))
    (SETQ NO-RELATIONS (QUOTE NO-RELATIONS))
    (SETQ MAYBE-RELATIONS (QUOTE MAYBE-RELATIONS))
    (SETQ CLASS-OBJECTS (QUOTE CLASS-OBJECTS))
    (SETQ CLASS-NAMES-ORDERING (QUOTE CLASS-NAMES-ORDERING))
    (SETQ IN (QUOTE IN))
    (SETQ UNTIL (QUOTE UNTIL))
    (SETQ CLASS-RELATIONS (QUOTE CLASS-RELATIONS))
    (SETQ DO (QUOTE DO))
    (SETQ FOR (QUOTE FOR))
    (SETQ FROM (QUOTE FROM))
    (SETQ TO (QUOTE TO))
    (SETQ USING (QUOTE USING))
    (SETQ LIST-OF-POSSIBLE-CLASS-NAMES NIL)
    (SETQ FILE-NAME (ASK-FOR-2])

\4The BEING version uses a list of initializations to do at LOAD time.  Numeric
suffixes merely indicate some of the new, specialized BEINGs' names.\*

  (RPAQQ GLOBAL-INITIALIZATION-LIST (
          (SETQ TYPE-OF-C-F CLASSIFICATORY-CONCEPT-FORMATION)
	  (SETQQ HALT HALT)
	  (SETQQ NAME-OF-CLASS NAME-OF-CLASS)
	  (SETQQ SET-OF-POSSIBLE-NAMES-OF-CLASS NIL)
	  (SETQQ ALPHORDER ALPHORDER)
  	  (SETQQ NOTHING NOTHING)
	  (SETQQ POSSIBLE-NAME-OF-CLASS POSSIBLE-NAME-OF-CLASS)
	  (SETQQ MAYBE-RELNS-30 MAYBE-RELNS-30)
	  (SETQQ YES-RELNS-28 YES-RELNS-28)
	  (SETQQ ELEMENT-RELNS-15 ELEMENT-RELNS-15)
	  (SETQQ NO-RELNS-29 NO-RELNS-29)
	  (SETQQ POSSIBLE-NAME-OF-CLASS-OBJECTS-20 POSSIBLE-NAME-OF-CLASS-OBJECTS-20)
	  (SETQQ ELEMENT-OBJECTS-11 ELEMENT-OBJECTS-11)
	  (SETQQ CLASS-MAYBE-RELNS-37 CLASS-MAYBE-RELNS-37)
	  (SETQQ CLASS-NO-RELNS-36 CLASS-NO-RELNS-36)
	  (SETQQ CLASS-YES-RELNS-35 CLASS-YES-RELNS-35)
	  (SETQQ CLASS-CLASSNAME-34 CLASS-CLASSNAME-34)
	  (SETQQ CLASS-OBJECTS-33 CLASS-OBJECTS-33)
	  (SETQQ ??? ???)))

  (PUTPROPS CF-1 IDEN ((( ( (MEMBER LI (QUOTE ((CONCEPT FORMATION)
						   (CF-1)
						   (CONCEPT LEARNING)
						   (FORM CONCEPTS)
						   (LEARN CONCEPTS)
						   (LEARNS CONCEPTS)
						   (FORMS CONCEPTS))))))
			( CF-1))) 
                 EXPLICIT-ARGS-CHECK T 
                 WHAT ( A SPECIALIZED BEING WHICH DOES
			      ( LEARN HOW TO IMPOSE A CONCEPT STRUCTURING UPON A DOMAIN; LEARN HOW TO 
				     CHARACTERIZE, OR AT LEAST DISTINGUISH, VARIOUS CONCEPTS)) 
                 HOW ( BY CHOOSING THE DESIRED TYPE OF CONCEPT FORMATION CALLED FOR, AND THEN CARRYING IT OUT) 
                 WHY ( CONCEPT-LEARNING IS NECESSARY TO CONCEPT KNOWLEDGE AND CONCEPT-FORMATION IS TOO GENERAL TO 
			    USE AS IT IS) 
                 MAIN-EFFECTS ((( ABLE PUP ( LEARN CONCEPTS))
				( CF-1))) 
                 WHEN (((MEMBER TYPE-OF-C-F ABLE-PUP-LIST)
			-70
			( BECAUSE IF WE CAN ALREADY DO ( TYPE-OF-C-F)
			       THEN WE SHOULDNT TRY TO DO IT OVER AGAIN))
		       ((MEMBER (QUOTE (CHARACTERIZE CLASSES))
				PUP-WANTS-LIST)
			88
			(QUOTE (BECAUSE CONCEPT FORMATION IS A GOOD WAY TO GET A CHARACTERIZATION OF CLASSES)))
		       (T (COND (NEW-INFO-LIST -60)
				(T 40))
			  (QUOTE (BECAUSE NEW INFORMATION MIGHT ALTER OUR COURSE OF ACTION)))) 
                 \4META-CODE\* (TEMPORARILY (PAD-2)) 
                 PRE-REQUISITES (( AWARE USER ( PUP IS ABOUT TO WORK ON CONCEPT FORMATION))
				 ( AWARE USER ( THE TYPE OF CONCEPT FORMATION PUP IS ABOUT TO WORK ON IS
							    ( TYPE-OF-C-F)))) 
                 POST-REQUISITES (( AWARE USER ( PUP HAS THOUGHT ABOUT THE ( TYPE-OF-C-F)
							     TYPE OF CONCEPT-FORMATION))) 
                 DEMONS ( INFERENCE-DEMONS ATTENTION-DEMONS) 
                 AFFECTS () 
                 COMPLEXITY: (.8 .8 .8 .8 .1) 
                 GENERALIZATIONS (CONCEPT-FORMATION ATTEND LEARN INDUCTIVE-INFERENCE) 
                 SPECIALIZATIONS NIL 
                 ALTERNATIVES ((GRAMMATICAL-INFERENCE PATTERN-RECOGNITION SIMULATED-EVOLUTION)) 
                 BEING T 
                 EXPLICIT-ARGS (DUMMY-ARGUMENT-3 DUMMY-ARGUMENT-2 DUMMY-ARGUMENT-1))

\4Notice that both versions' CF functions just call PARTITION-A-DOMAIN\*

(PARTITION-A-DOMAIN
  [LAMBDA NIL
    (PROG NIL
      START-OF-SERIES
          (INPUT-1-ELEMENT)
          (COND
            ((HAS-NAME)
              (INPUT-2-CLASS-NAME))
            (T (DETERMINE-1-CLASS-NAME)))
          (COND
            ((EQUAL CLASS-NAME (QUOTE HALT))
              (HALT-1))
            (T (PRINT (QUOTE (I NOW KNOW)))
               [FOREACH (QUOTE NAME) IN LIST-OF-POSSIBLE-CLASS-NAMES
                  DO (QUOTE (PROGN (PRINT NAME)
                                   [COND
                                     ((GETP NAME CLASS-OBJECTS)
                                       (PRIN1 (QUOTE "OBJECTS "))
                                       (PRINT (GETP NAME CLASS-OBJECTS]
                                   [COND
                                     ((GETP NAME YES-RELATIONS)
                                       (PRIN1 (QUOTE "MUST HAVE "))
                                       (PRINT (GETP NAME YES-RELATIONS]
                                   [COND
                                     ((GETP NAME NO-RELATIONS)
                                       (PRIN1 (QUOTE "MUSNT HAVE "))
                                       (PRINT (GETP NAME NO-RELATIONS]
                                   (COND
                                     ((GETP NAME MAYBE-RELATIONS)
                                       (PRIN1 (QUOTE "MAY HAVE "))
                                       (PRINT (GETP NAME 
                                                    MAYBE-RELATIONS]
               (GO START-OF-SERIES])

\4The BEING version of PARTITION is quite similar.  Notice the use of comments:
though written by PUP6 for its own use, they are also meaningful to the user.
Below, \*ELEMENT\4 refers to a scene, and \*CLASS\4 refers to a concept model.\*

  (PUTPROPS PAD-2 
	  	  IDEN ((( ( (MATCH ( PARTITION A DOMAIN)
					LI)))
			 ( PAD-2))
			(( ( (MATCH ( DIVIDE A DOMAIN UP)
					LI)))
			 ( PAD-2))) 
                  IMPLICIT-ARGS (PRESULT) 
                  EXPLICIT-ARGS-CHECK T 
                  WHAT ( A SPECIALIZED BEING WHICH DOES
			       ( DIVIDE A DOMAIN INTO SUBDOMAINS; USUALLY THESE WILL BE DISJOINT, AND THEIR UNION 
				      WILL BE THE ENTIRE DOMAIN)) 
                  HOW ( BY BUILDING UP THE PARTITION GRADUALLY, BY ADDING TO OUR KNOWLEDGE OF THE PARTITION ONE 
			     PAIR AT A TIME; HERE A PAIR IS <ELEMENT, CLASS-NAME>) 
                  WHY ( BECAUSE PUP MUST PARTITION A DOMAIN INTO CLASSES, AND 
			     PARTITION-A-DOMAIN IS TOO GENERAL TO USE AS IT IS) 
                  MAIN-EFFECTS ((( PARTITIONED DOMAIN)
				 ( PAD-2))) 
                  WHEN ((PARTITIONED-DOMAIN-LIST -100 ( BECAUSE WE ALREADY HAVE PARTITIONED DOMAIN))
			((NULL PARTITIONED-DOMAIN-LIST)
			 20
			 ( BECAUSE PUP HAS NOT YET PARTITIONED DOMAIN, SO IT IS PLAUSIBLE TO DO IT NOW))) 
                 \4META-CODE\* (PROG NIL 
				LABEL-1 
 				  (TAKE-HOLD-OF-3 ELEMENT-4)
				  (COND ((HAS-NAME-5 ELEMENT-4 (COMMENT PARTITION-BY-TAKE-ELE-AND-CLASS))
					      (TAKE-HOLD-OF-6 NAME-OF-CLASS)
					      (MODIFY-STRUCTURE-7 NAME-OF-CLASS))
					   (T (GET-HOLD-OF-8 NAME-OF-CLASS)
					        (MODIFY-STRUCTURE-9 NAME-OF-CLASS)))
				  (COND ((IS-OF-TYPE-61 ARG1 (COMMENT BREAKAWAY))
 					     (COMMENT FINALIZATION OF LOOP STARTING AT LABEL-1 MAY GO HERE))
					   (T (FOREACH NAME IN SET-OF-POSSIBLE-NAMES-OF-CLASS DO
						     (PROGN (PRINT NAME)
								(COND ((GETP NAME CLASS-OBJECTS-33)
								            (PRIN1 "OBJECTS ")
								            (PRINT (GETP NAME CLASS-OBJECTS-33))))
								(COND ((GETP NAME CLASS-YES-RELNS-35)
								            (PRIN1 "MUST HAVE ")
								            (PRINT (GETP NAME CLASS-YES-RELNS-35))))
								(COND ((GETP NAME CLASS-NO-RELNS-36)
								            (PRINT (GETP NAME CLASS-NO-RELNS-36))))
								(COND ((GETP NAME CLASS-MAYBE-RELNS-37)
								            (PRIN1 "MAY HAVE ")
								            (PRINT (GETP NAME CLASS-MAYBE-RELNS-37))))
								(TERPRI)
								T))
						(GO LABEL-1)))
				  (COMMENT SEE: THERE IS NO INFINITE LOOP IN THIS PROG AFTER ALL; WE ARE 
					   EXITING IT!)) 
                  DEMONS ( FRINGE-OF-CONCIOUSNESS-DEMON) 
                  COMPLEXITY: (.8 .8 .8 .8 .1) 
                  GENERALIZATIONS (PARTITION-A-DOMAIN  MAP BUILD-FUNCTION) 
                  SPECIALIZATIONS NIL 
                  ALTERNATIVES ( DIVIDE-UP DISCRETIZE) 
                  BEING T 
                  EXPLICIT-ARGS (DUMMY-ARGUMENT-3 DUMMY-ARGUMENT-2 DUMMY-ARGUMENT-1) 
                  AFFECTS ( ( ELEMENT-4 POSSIBLE CALLED)
				  ( ELEMENT-4 POSSIBLE CALLED)
				  ( IN POSSIBLE CALLED)))

\4Here are the hand versions of INPUT-1-ELEMENT and HAS-NAME\*

(INPUT-1-ELEMENT
  [LAMBDA NIL
    (PRINT (QUOTE (I AM READY FOR A SCENE)))
    (SETQ ELEMENT (READ))
    (SETQ LIST-OF-OBJECTS-OF-ELEMENT (CORRESPONDING-OBJECTS-PART))
    (SETQ SET-OF-RELATIONS (CORRESPONDING-RELATIONS-PART))
    (SETQ CLASS-NAME (CAR ELEMENT])

(HAS-NAME
  [LAMBDA NIL
    (NOT (EQUAL (CAR ELEMENT)
                (QUOTE ?])

\4The PUP6 versions include extra BEINGS, STATIC-SCENE and ELEMENT, which
have no control function;  rather,  their role  is  analogous to a data structure.
PUP6 uses the name TAKE-HOLD-OF-3 instead of INPUT-1-ELEMENT.\*

  (PUTPROPS STATIC-SCENE-10 IDEN ((( ( (EQUAL LI (LIST STATIC-SCENE-10))))
				   ( STATIC-SCENE-10))) 
                            \4META-CODE\* (STRUCTURE (OBJECTS SET O)
						 (CLASS-NAME NAME N)
						 (STATIC RELATIONS S BETWEEN OBJECTS)) 
                            COMPLEXITY: (.8 .8 .8 .8 .1) 
                            DATA-STRUCTURE T 
                            BEING T 
                            WHAT ( A SPECIALIZED BEING WHICH DOES NIL)
                            WHY (SCENE IS TOO GENERAL TO USE AS IT IS) 
                            GENERALIZATIONS (SCENE) 
  (PUTPROPS ELEMENT-4 IDEN ((( ( (EQUAL ( ELEMENT-4)
					    LI)))
			     ( ELEMENT-4))) 
                      EXPLICIT-ARGS-CHECK T 
                      WHAT ( A SPECIALIZED BEING WHICH DOES
				   ( A STRUCTURE WHICH IS A MEMBER OF A LARGER STRUCTURE)) 
                      COMPLEXITY: (.8 .8 .8 .8 .1) 
                      DATA-STRUCTURE (ACCESS (((SOME-PART-OF-16 X)
					       ACCESSES
					       (STATIC RELATIONS S BETWEEN OBJECTS))
					      ((SOME-PART-OF-14 X)
					       ACCESSES
					       (CLASS-NAME NAME N))
					      ((SOME-PART-OF-12 X)
					       ACCESSES
					       (OBJECTS SET O)))) 
                      BEING T 
                      EXPLICIT-ARGS (DUMMY-ARGUMENT-3 DUMMY-ARGUMENT-2 DUMMY-ARGUMENT-1) 
                      WHY (ELEMENT IS TOO GENERAL TO USE AS IT IS) 
                      \4META-CODE\* (STRUCTURE (OBJECTS SET ELEMENT-OBJECTS-11)
					   (CLASS-NAME NAME ELEMENT-CLASSNAME-13)
					   (STATIC RELATIONS ELEMENT-RELNS-15 BETWEEN OBJECTS)) 
                      GENERALIZATIONS (ELEMENT) 
  (PUTPROPS HAS-NAME-5 EXPLICIT-ARGS (ARG1 DUMMY-ARGUMENT-2 DUMMY-ARGUMENT-1) 
                       EXPLICIT-ARGS-CHECK T 
                       WHAT ( A SPECIALIZED BEING WHICH DOES ( SEE IF ( ARG1)
									  IS OF THE TYPE SPECIFIED. THE PARTICULAR TYPE 
									  IS DELINEATED BY THE SPECIAL KNOWLEDGE
									  ( DUMMY-ARGUMENT-2))) 
                       HOW ( USE ( DUMMY-ARGUMENT-2)
				  DETAILS TO SEE IF IT CONTAINS ( ARG1)) 
                       WHY ( WE MUST BE ABLE TO TEST AN ARG1 ( ARG1)
				  AND SEE IF IT BELONGS TO THE TYPE ( DUMMY-ARGUMENT-2)
				  AND IS-OF-TYPE IS TOO GENERAL TO USE AS IT IS) 
                       \4META-CODE\* (PROGN (COMMENT IN ALL CALLS TO DATE, ARG1 IS INSTANTIATED AS ELEMENT-4)
					(NOT (EQUAL (CAR ARG1)
						    ???))) 
                       COMPLEXITY: (.8 .8 .8 .8 .1) 
                       SPECIALIZATIONS NIL 
                       PREDICATE T 
                       BEING T 
                       GENERALIZATIONS (IS-OF-TYPE) 
                       AFFECTS ( ( IN POSSIBLE CALLED)
				       ( ELEMENT-4 POSSIBLE CALLED)))
  (PUTPROPS TAKE-HOLD-OF-3 EXPLICIT-ARGS (ARG1) 
                           EXPLICIT-ARGS-CHECK T 
                           NLAMBDA T 
                           WHAT ( A SPECIALIZED BEING WHICH DOES ( TAKE THE ARG1 ( ARG1)
									      IN A TRIVIAL WAY; EITHER BY ACCESSING IT 
									      OR BY READING IT IN)) 
                           HOW ( LOOK AROUND A LITTLE; IF IT ISNT FOUND TRIVIALLY, THEN ASK THE USER TO GIVE
				      ( ARG1)
				      TO US) 
                           WHY ( PUP WANTS ( ARG1)
				      ,AND WE DON'T HAVE TO DO ANY COMPUTING TO GET IT AND TAKE-HOLD-OF IS TOO GENERAL 
				      TO USE AS IT IS) 
                           COMPLEXITY: (.8 .8 .8 .8 .1) 
                           BEING T 
                           \4META-CODE\* (PROGN (COMMENT IN ALL CALLS TO DATE, ARG1 IS INSTANTIATED AS ELEMENT-4)
					    (PROGN (PRINT (COMMENT READY TO ACCEPT BRAND NEW ELEMENT-4))
						   (SET ARG1 (READ))
						   (SETQ ELEMENT-OBJECTS-11 (SOME-PART-OF-12 (EVAL ARG1)))
						   (SETQ ELEMENT-CLASSNAME-13 (SOME-PART-OF-14 (EVAL ARG1)))
						   (SETQ ELEMENT-RELNS-15 (SOME-PART-OF-16 (EVAL ARG1)))
						   T)) 
                           GENERALIZATIONS (TAKE-HOLD-OF) 
                           AFFECTS ( 
					   ( ELEMENT-4 POSSIBLE CALLED)
					                                   
					   ( ELEMENT-OBJECTS-11 POSSIBLE CALLED)
					   ( ELEMENT-CLASSNAME-13 POSSIBLE CALLED)
					   ( ELEMENT-RELNS-15 POSSIBLE CALLED)))

\4The following is a very low-level function found in the hand-coded version,
which must insert a key contradictory feature into a model's set of NO relations.\*

(DELETE-1-3-1
  [LAMBDA NIL
    (PROG (TEMPORARY-NO-RELATIONS)
          (SETQ TEMPORARY-NO-RELATIONS (GETP CLASS-NAME NO-RELATIONS))
          (SETQ TEMPORARY-NO-RELATIONS (PULLOUT RELATION 
                                             TEMPORARY-NO-RELATIONS))
          (PUT CLASS-NAME NO-RELATIONS TEMPORARY-NO-RELATIONS])

\4The version PUP6 writes includes the test as well:   there must be
some feature in the current NO relations set which is also present
in  the  scene  (that is,  located on the list  ELEMENT-RELNS-15).\*

  (PUTPROPS CONDITIONAL-DELETION-54 IDEN ((( ( ( ( ( (EQUAL (CAR LI)
								   (QUOTE DELETE)))))))
					   ( CONDITIONAL-DELETION-54 (TRANSLATE (IN (CDR LI))
										      T)))) 
                                    EXPLICIT-ARGS (DUMMY-ARGUMENT-2 DUMMY-ARGUMENT-1) 
                                    EXPLICIT-ARGS-CHECK T 
                                    WHAT ( A SPECIALIZED BEING WHICH DOES
						 ( PERHAPS WE WILL REMOVE AN ELEMENT FROM CLASS-NO-RELNS-29 , 
							SOMETHING IN BOTH ELEMENT-RELNS-15
							AND ALREADY ON THE CLASS-NO-RELNS-29 LIST
                                                        IF SUCH AN ENTITY CAN BE FOUND))
                                    HOW ( WE WILL SEARCH FOR SUCH AN ELEMENT, AND USE PULLOUT)
                                    WHY ( IT WOULD BE CONTRADICTORY FOR SUCH AN ELEMENT TO REMAIN ON THIS LIST 
					       IF IT IS ON THE LIST AND ALSO ON THE ELEMENT-RELNS-15 LIST AT THE SAME 
					       TIME. WE HAD TO SPECIALIZE TO THE CONDITIONAL-DELETION BEING BECAUSE
					       CONDITIONAL-DELETION IS TOO GENERAL TO USE AS IT IS)
                                    \4META-CODE\* (PROGN (SETQ RESULT-6 (SETINTERSECTION (GETP NAME-OF-CLASS 
											   CLASS-NO-RELNS-36)
										     ELEMENT-RELNS-15))
						     (COND (RESULT-6 (PUT NAME-OF-CLASS CLASS-NO-RELNS-36
									  (PULLOUT RESULT-6 (GETP NAME-OF-CLASS 
												  CLASS-NO-RELNS-36))))
							   (T (SETQ RESULT-6 NIL)))) 
                                    COMPLEXITY: (.8 .8 .8 .8 .1) 
                                    GENERALIZATIONS (CONDITIONAL-DELETION  MODIFY-STRUCTURE) 
                                    BEING T 
                                    AFFECTS ( ( ELEMENT-RELNS-15 POSSIBLE CALLED)))
.END
THIS GETS DOTTED IF NEEDEDZzzzzzzzz
 END
 PAGE FRAME 54 HIGH 89 WIDE
 TITLE AREA HEADING LINES 1 TO 3
 AREA TEXT LINES 4 TO 53
 TITLE AREA FOOTING LINE 54
 NOFILL
 PAGE←PAGE-1
.BEGIN SELECT 8 NOFILL PREFACE 0 MILLS
.SKIP TO COLUMN 1
.SSEC(Flow Chart of Target Program [CF]   including names of major functions)
.TURN OFF "↑↓→←α[]{}"

⊂αααα⊃      ⊂ααααααααααααααααααααααα⊃
~ CF εααααα→λ    (INITIALIZE-1)     ~
%αααα$      %ααααααααααπαααααααααααα$
                       ~
                       ~  enter the PARTITION-A-DOMAIN loop
                       ↓
     ⊂α⊃    ⊂ααααααααααααααααααααααα⊃
     ~1εααα→λ Accept the description~
     %α$    ~     of a scene        ~               ⊂α⊃
⊂αααααααααα→λ   (INPUT-1-ELEMENT)   ~               ~2~
~           %ααααααααααπαααααααααααα$               %π$
~                      ~                             ~
~                      ↓                             ↓
~           ⊂ααααααααααααααααααααααα⊃     ⊂ααααααααααααααααααααααα⊃
~           ~ Does the scene have a ~ YES ~  Has the scene been   ~ YES
~           ~       name?           εαααα→λ previously described? εααααα⊃
~           ~      (HAS-NAME)       ~  ⊂α→λ(CHECK-FOR-OLD-NAME)   ~     ↓
~           %ααααααααααπαααααααααααα$  ↑  %ααααααααααπαααααααααααα$     ~
~                      ~NO             ~             ~NO                ~
~                      ~               ~             ↓                  ~
~                      ~               ~  ⊂ααααααααααααααααααααααα⊃     ~
~                      ~               ~  ~ Insert the description~     ~
~                      ~     (NO-GUESS)~  ~  of the scene in the  ~     ~
~                      ~      AND SCENE~  ~      object list      ~     ~
~                      ~       DEFINED ~  ~      (NEW-NAME)       ~     ~
~                      ~          ⊂αααα$  %ααααααααααπαααααααααααα$     ~
~                      ~          ~                  ~                  ~
~                      ↓          ↑                  ↓                  ~
~(NO-GUESS) ⊂ααααααααααααααααααααααα⊃               ⊂α⊃                 ~
~AND SCENE  ~ Make a guess at what  ~   GUESS       ~1~                 ~
~UNDEFINED  ~the object is, based on~ CORRECTLY     %α$                 ~
~←ααααααααααλ    previous scenes    ε→αααααααα⊃      ~                  ~
~           ~ (DETERMINE-CLASSNAME) ~         ↓      ↑                  ~
~           %ααααααααααπαααααααααααα$      ⊂ααααααααααααααααααααααα⊃    ~
~                      ~MADE WRONG         ~ Correlate this scene  ~    ~
~                      ~GUESS              ~   with other scenes   ~←ααα$
~           ⊂αααααααααα↓αααααααααααα⊃      ~(PATCH-OLD-DESCRIPTION)~
~SCENE      ~   Put in MUSTs and    ~      %ααααααααααααααααααααααα$
~UNDEFINED  ~   MUSTNOTs on scene   ~   ⊂α⊃
%αααααααααα←λ      deviations       εαα→λ2~
            ~ (TIGHTEN-CONSTRAINTS) ~   %α$
            %ααααααααααααααααααααααα$
.E
.TURN ON "↑↓α"
.ASEC(Appendix 5: Excerpts from the PUP6-User dialogue creating CF)

.TURN ON "\" FOR "%"
.FILL

Here are fragments of the dialogue which the user went  through  with
PUP6  to  generate  the  CF  program.
Keep in mind that the entire dialogue occupied half a million characters,
so only 3% of it is presented here.  Even these numbers are deceptively
small; they assume the user never interrupts. If he does, the size of the
interaction can swell 
by two orders of magnitude! As an example of this, a
four line long patch of the dialogue, near the beginning, was re-run in
a mode which allowed the user to interrupt after each BEING transferred
control, and query (ask some of the thirty questions) BEINGs as they ran.
The uncommented patch is set off by rows of asterisks, on page A5.2.
The expanded version occupies pages A5.13 to A5.20.
The user's responses are set in \2Bold face type\*,
and the author's meta-comments are in \7small type\*.
Frequently, the user is asked to pick a name for a new BEING. He is
presented with a set of plausible choices, from which he may deviate.
This verbosity obscures the heart of the dialogue, so only the first
such naming is tolerated below; the others were deleted.
Names of new, specialized 
versions of existing BEINGs are typically suffixed
by a number.
.NOFILL
.SELECT 1


←\2ENTER(PUP6)\*

PUP: How often should I let you interrupt me? \2Never.\*

PUP: I want any task.
USER: \2Write a program which does concept formation.\*
PUP: I am about to write a program for specialized CONCEPT-FORMATION.
PUP: Give me a proper name for this program. (I suggest C-F, CONCEPT, C, CF)
	What you call concept formation, I call concept-formation.
USER: \2CF\*
PUP: PUP and USER may refer to this new specialized version of concept-formation as CF-1.

.EPAGE←PAGE
.BEGIN NOFILL GROUP  NARROW 2,7  PREFACE 0 MILLS  TURN ON "→∞"  SELECT 8
.ONCE TURN OFF "α"
⊂∞α→⊃
.SELECT 1
⊗8~⊗*
⊗8~⊗*  MOVE CURSOR TO  CF-1 TYPE OF  CONCEPT-FORMATION→⊗8~⊗*
⊗8~⊗*→⊗8~⊗*
⊗8~⊗*  PUP: Sorry to bother you, but I can no longer defer this Boolean type of decision:→⊗8~⊗*
⊗8~⊗*    (SUBJECT-SPECIFIC BEHAVIOR MAY BE REQUIRED OF CF-1)→⊗8~
~⊗*    Should I discuss ramifications? \2Yes\*→⊗8~
~⊗*  PUP: Affirmative: ths would force CF to mimic different human subjects.→⊗8~
~⊗*		This would be done by reading in parameters for each individual.→⊗8~
~⊗*		I can't wait because every part of CF would then be parameterized.→⊗8~
~⊗*	Negative: In this case, there would be no action to take.→⊗8~
~⊗*       Since the decision is Boolean, just answer Yes, No, Unsure, or Details: \2No\*→⊗8~
~⊗*  PUP: Nothing need be done now. I am ready to move on.→⊗8~⊗*
.SELECT 8
.ONCE TURN OFF "α"
%∞α→$
.TURN OFF "∞→"
.END
.XGENLINES←XGENLINES-2

PUP: I am temporarily replacing the task "specialized CONCEPT-FORMATION" by the
	task "specialized PARTITION-A-DOMAIN".
⊗7Pup asks for a name for the new task; the user replies "PAD". Henceforth, we shall omit naming.⊗*

PUP:  CF-1 is not called anywhere.   Its meta-code is now   (TEMPORARILY (PAD-2)).

.FILL
\7 CF-1 has been made into a BEING. In addition to its Meta-code part,
most of its other parts have been filled in.
The full,  long  definition  contains  much  bookkeeping  but
nothing  of  relevance  to  tell  the  user.\*
.NOFILL

MOVE CURSOR TO  PAD-2 TYPE OF  PARTITION-A-DOMAIN

PUP: Sorry to bother you, but I can no longer defer this Some-of decision:
	Build up a partition of a domain by some of the following 3 activities:
		Take element of domain, get the name of the class it belongs to;
		Take class name, get the names of the elements it has;
		Take (element,classname) ordered pair and add it to partition.
	Since the decision is some-of, type any ordered subset of A,B,C, where
		(A .... PARTITION-BY-TAKE-ELE-AND-CLASS)
		(B .... PARTITION-BY-TAKE-CLASS-GET-ELE)
		(C .... PARTITION-BY-TAKE-ELE-GET-CLASS)

	For example, (B A) would mean that the 2nd and 1st items are relevant.
	Should I discuss ramifications? \2No.\*
USER: \2(A C)\*
.FILL
\7<TAKE involves trivial accessing or reading in; 
 GET involves working to obtain, e.g., 
by searching or computing or guessing-and-checking;
ELE refers to a scene; CLASS refers to the model of a concept.>\*
.NOFILL
.SELECT 6

PUP: At this point, I almost recommended that we structure a list, but have decided against it.
	The structure would have consisted of a division into two sublists, called
	         PARTITION-BY-TAKE-ELE-AND-CLASS-PART-OF-PARTITION-LIST sublist, and
	  	 PARTITION-BY-TAKE-ELE-GET-CLASS-PART-OF-PARTITION-LIST sublist.
	I decided against because PARTITION-LIST needn't exist, and because 2 parts is not many.

PUP: PAD-2 became (SOME-OF A B C) which became (A C) which is understood to mean
 (REPEATEDLY (TAKE-HOLD-OF ELEMENT)
	(COND ((IS-OF-TYPE ELEMENT (COMMENT PARTITION-BY-TAKE-ELE-AND-CLASS))
                     (TAKE-HOLD-OF NAME-OF-CLASS)
                     (MODIFY-STRUCTURE NAME-OF-CLASS))
                (T 
		     (GET-HOLD-OF NAME-OF-CLASS)
                     (MODIFY-STRUCTURE NAME-OF-CLASS))))

	Most of these BEINGs have to be specialized. Names for the specialized versions
	will be requested in preorder, as if the above code were a tree structure.

⊗7Pup gets names for Take-hold-of, Element, Is-of-type. Then it sees Element again, and asks:⊗*
PUP: Is this the same as a  ELEMENT  which we've already seen and named?
USER: \2Yes\*
PUP: Since ELEMENT-4 is the only known name for ELEMENT, I assume that is the one you want.
           Am I right? \2Yes\*   PUP: So the name chosen is ELEMENT-4 again.
\7From now on, even this level of naming detail will be omitted. All the general BEINGs who want to
have specialized versions of themselves written obtain names for those versions. Then:⊗*
PAD-2 is called inside CF-1. Its meta-code is now filled in as:
(PROG NIL
  LABEL-1
        (TAKE-HOLD-OF-3 ELEMENT-4)
        (COND
            ((HAS-NAME-5 ELEMENT-4 (COMMENT PARTITION-BY-TAKE-ELE-AND-CLASS))
              (TAKE-HOLD-OF-6 NAME-OF-CLASS)
              (MODIFY-STRUCTURE-7 NAME-OF-CLASS))
            (T 
	     (GET-HOLD-OF-8 NAME-OF-CLASS)
             (MODIFY-STRUCTURE-9 NAME-OF-CLASS)))
          (GO LABEL-1)
          (COMMENT INFINITE LOOP IN THIS PROG))))

(PAD-2 redefined) \7<as a BEING>\*

MOVE CURSOR TO  ELEMENT-4 TYPE OF  ELEMENT
PUP: Sorry to bother you, but I can no longer defer this Definition decision:
	 WHAT IS AN ELEMENT?
	Please just type in the definition of ELEMENT-4.
	Should I discuss ramifications?  \2No\*  \7Henceforth, this will be omitted\*
USER: \2(A description of a static scene)\*

⊗7Pup knows about scenes,and uses its knowledge of  the adjective Static to remove all 
Opposite(Static)=Active subparts from the description of a Scene. This leaves the following:⊗*
ELEMENT-4 is used 2 times inside PAD-2. Its meta-code is now filled in as:
    (STRUCTURE (OBJECTS SET O)
	               (CLASS-NAME NAME N)
	               (STATIC RELATIONS S BETWEEN OBJECTS))))

MOVE CURSOR TO  HAS-NAME-5 TYPE OF  IS-OF-TYPE
PUP: Sorry to bother you, but I can no longer defer this Definition decision:
      How do we know when the 'IS-OF-TYPE' Predicate is TRUE, and when it is FALSE? 
        I assume that the user will type in a logical sentence whose truth is equivalent to it.
	Please just type in the definition of HAS-NAME-5.  The expression you type in
	should be a predicate, which is true iff ELEMENT-4 is of the
	"Partition by take ele and class" type, and should be false iff it isnt of that type.
USER: \2(The front part of ARG1 isnt ???)\*
PUP: Is ??? a literal constant (whose value should be itself)? Reply Yes or No: \2Yes\*

HAS-NAME-5 is used in PAD-2 with argument ELEMENT-4. Its args and meta-code are filled in as:
(LAMBDA (ARG1)
    (COMMENT In all calls to date, ARG1 is instantiated as ELEMENT-4)
    (NOT (EQUAL (CAR ARG1)  ???)))

MOVE CURSOR TO  TAKE-HOLD-OF-3 TYPE OF  TAKE-HOLD-OF
PUP: Sorry to bother you, but I can no longer defer this Dichotomy decision:
	To take hold of ELEMENT-4, do I do a Read or an Assignment?
       ...HMMM...AHA!!!! I'VE RESOLVED IT MYSELF!!! NO NEED TO INTERACT WITH THE SLOW
	USER CHANNEL AFTER ALL!!!    I have proven that I must Read it in here.
PUP: After Reading in ELEMENT-4, I am going to assign OBJECTS part of static-scene to
	Some-part-of ARG1 which will be assigned the value ELEMENT-4 read in.
	Give me a name for the OBJECTS part and for the SOME-PART-OF function-...
⊗7We skip this naming, as usual.⊗*
TAKE-HOLD-OF-3 is used inside PAD-2 with argument ELEMENT-4. Its args and meta-code parts are:
(NLAMBDA (ARG1)
    (COMMENT In all calls to date, ARG1 is instantiated as ELEMENT-4)
    (PRINT (COMMENT READY TO ACCEPT BRAND NEW ELEMENT-4))
    (SET ARG1 (READ))
    (SETQ ELEMENT-OBJECTS-11 (SOME-PART-OF-12 (EVAL ARG1)))
    (SETQ ELEMENT-CLASSNAME-13 (SOME-PART-OF-14 (EVAL ARG1)))
    (SETQ ELEMENT-RELNS-15 (SOME-PART-OF-16 (EVAL ARG1)))
    T))

NAME-OF-CLASS is not a BEING yet. I have things to do when it becomes one, however.
MOVE CURSOR TO  TAKE-HOLD-OF-6 TYPE OF  TAKE-HOLD-OF
PUP: An assignment which set the value of NME-OF-CLASS was done earlier in the flow;
	should a new value of NAME-OF-CLASS be read in at this point in the flow? \2No\*
TAKE-HOLD-OF-6 is used inside PAD-2 with argument NAME-OF-CLASS. Its args and meta-code are:
(NLAMBDA (ARG1)
    (COMMENT In all calls to date, ARG1 is instantiated as NAME-OF-CLASS)
    (COMMENT Little to do here; just one simple assignment to an already-existing value)
    (SET ARG1 OBVIOUS-KNOWN-VALUE-OF-NAME-OF-CLASS)))

MOVE CURSOR TO  GET-HOLD-OF-8 TYPE OF  GET-HOLD-OF
PUP: Sorry to bother you, but I can no longer defer this Some-of decision:
    (COMPUTE   SEARCH    GENERATE-AND-TEST) as methods to get NAME-OF-CLASS.
	Since the decision is Some-of, type any ordered subset of A,B,C, where
	(A .... COMPUTE)
	(B .... SEARCH)
	(C .... GENERATE-AND-TEST)
USER: \2(B)\*
PUP: I can encode a nice algorithm here if you can give me a list of all the values that
	could conceivably occur as names on the list SET-OF-POSSIBLE-NAMES-OF-CLASSES.
	If this is not meaningful or possible, reply NIL.
USER: \2NIL\*
PUP: SIGH.
PUP: Sorry to bother you, but I can no longer defer this Boolean decision:
     DOES AN ALGORITHM ALREADY EXIST WHICH GETS PRECISELY NAME-OF-CLASS?
	Since the decision is Boolean, just reply Yes or No. \2No\*
PUP: OK, there is nothing to do now. Ready to move on.

The function GET-HOLD-OF-8 willhave the following form:
(FOREACH POSSIBLE-NAME-OF-CLASS IN SET-OF-POSSIBLE-NAMES-OF-CLASS  DO
	(TEST POSSIBLE-NAME-OF-CLASS (COMMENT FOR SATISFACTION OF GOAL CRITERIA)))
        (PRIN1 "MY GUESS FOR THIS IS ")
        (PRINT POSSIBLE-NAME-OF-CLASS))

Many of the BEINGs mentioned will want to replace themselves by specialized versions.
MOVE CURSOR TO  FOREACH-17 TYPE OF  FOREACH
PUP: Sorry to bother you, but I can no longer defer this Boolean Decision:
      I assume that I stop after examining all POSSIBLE-NAMES-OF-CLASS in 
      SET-OF-POSSIBLE-NAMES-OF-CLASS ; Do I also stop after some condition 'C' becomes true?
	Since the decision is Boolean, just reply Yes or No? \2Yes\*
	Now type in a predicate equivalent to this Until-condition 'C':
USER: \2TEST-18 Succeeded.\*         ⊗7That is, halt if we find a matching model.⊗*
PUP: Understood. Moving On. FOREACH-17 is used inside GET-HOLD-OF-8, inside PAD-2.
Its arguments are POSSIBLE-NAME-OF-CLASS, SET-OF-POSSIBLE-NAMES-OF-CLASS, and the
form (TEST-18 POSSIBLE-NAME-OF-CLASS (COMMENT for satisfaction of goal criteria))).
The args and meta-code parts of FOREACH-17 are now filled in as:
(NLAMBDA (ARG1 DUMMY-ARGUMENT-2 ARG3 DUMMY-ARGUMENT-1 ARG5)
   (COMMENT In all calls to date, ARG1 is instantiated as POSSIBLE-NAME-OF-CLASS)
   (COMMENT In all calls to date, ARG3 is instantiated as SET-OF-POSSIBLE-NAMES-OF-CLASS)
   (COMMENT In all calls to date, ARG5 is instantiated as 
	 '(TEST-18 POSSIBLE-NAME-OF-CLASS  '(FOR SATISFACTION OF GOAL CRITERIA)))
   (PROG (RESULT-1)
            (SETQ EVAL-ARG3 (EVAL ARG3))
          LABEL-2
            (COND
              ((NULL EVAL-ARG3)
                (SET ARG1 FAILURE-VALUE)
                (RETURN EXHAUSTION-VALUE)))
            (SET ARG1 (CAR EVAL-ARG3))
            (SETQ EVAL-ARG3 (CDR EVAL-ARG3))
            (SETQ RESULT-1 (EVAL ARG5))
            (COND
	       ((NOT (EQUAL RESULT-1 NIL)) ⊗7This is the translation of "TEST-18 succeeded".⊗*
		(RETURN   UNTIL-CONDITION-VALUE))
	       (T (GO LABEL-2)))
	(COMMENT At the time that FOREACH-17 was coded, 
			UNTIL-CONDITION-VALUE was left undefined))))

MOVE CURSOR TO  TEST-18 TYPE OF  TEST
PUP: Sorry to bother you, but I can no longer defer this Boolean decision:
      SHOULD WE IMPLEMENT ERROR RECOVERY IN ANY FANCY WAY? \2No\*
	Nothing to do at this time, then. Ready to move on.
PUP: Sorry to bother you, but I can no longer defer this Dichotomy decision:
	Testing may have the character of comparing the object with some distinguished object.
	Testing may have the character of letting the object compete with its fellow
	    objects for supremacy. Object, in this case, means POSSIBLE-NAME-OF-CLASS.
	AHA!!!! I'VE RESOLVED IT MYSELF!!! NO NEED TO INTERACT WITH THE SLOW USER!!
	I do the testing by comparing the object against ELEMENT-4. Right? \2Yes\*

TEST-18 is used inside FOREACH-17 foreach loop, with argument ARG1 which will always
instantiate as POSSIBLE-NAME-OF-CLASS. The args and meta-code of TEST-18 are filled in as:
(LAMBDA (ARG1)
	(COMMENT In all calls to date, ARG1 is instantiated as POSSIBLE-NAME-OF-CLASS)
	(COMPARE-19  ARG1  ELEMENT-4))

⊗7Pup next fills in the body of Compare-19, as:⊗*

(LAMBDA (ARG1 ARG2)
   (COMMENT In all calls to date, ARG1 is instantiated as POSSIBLE-NAME-OF-CLASS)
   (COMMENT In all calls to date, ARG2 is instantiated as ELEMENT-4)
   ARG1
   ARG2
   (COMMENT ARG1 and ARG2 are here simply to cause PUP to insert comments about their bindings)
   (JOIN-23 (COMPARE-24 POSSIBLE-NAME-OF-CLASS-OBJECTS-20
			 ELEMENT-OBJECTS-11)
             (COMPARE-25 POSSIBLE-NAME-OF-CLASS-CLASSNAME-21 
			 ELEMENT-CLASSNAME-13)
             (COMPARE-26 POSSIBLE-NAME-OF-CLASS-RELNS-22 
			 ELEMENT-RELNS-15))))
.FILL  ONCE TURN ON "{}"
\7Here begins one of the sections discussed in section 7.4, and then treated
again on page {DPAGE} of this paper, 
namely the genesis of the MUSTNOT/MUST/MAY divisions.
The names used 
here differ slightly from those in the body of the paper.  The
 symbol # stands for "contradiction".\*
.NOFILL
.SELECT 6

MOVE CURSOR TO  JOIN-23 TYPE OF  JOINING-FUNCTION
PUP: Sorry to bother you, but I can no longer defer this PREDICATE DECISION:
        WHEN DO WE TERMINATE THE LOOP?
	Please type in a logical expression which is true when we should terminate
	the comparison loop, and false otherwise.
USER: \2(Any relation in POSSIBLE-NAME-OF-CLASS-RELNS-22 is 
		incompatible with ELEMENT-RELNS-15)\*
⊗7Pup now infers that the type of joining function required is simply an AND.⊗*
JOIN-23 is used inside COMPARE-19. It is conceptually just the function AND.
	Its args and meta-code parts are filled out as:
(LAMBDA (ARG1 ARG2 ARG3)
    (COMMENT In all calls to date, ARG1 is instantiated as
          (COMPARE-24  POSSIBLE-NAME-OF-CLASS-OBJECTS-20   ELEMENT-OBJECTS-11))
    (COMMENT In all calls to date, ARG2 is instantiated as
          (COMPARE-25  POSSIBLE-NAME-OF-CLASS-CLASSNAME-21 ELEMENT-CLASSNAME-13))
    (COMMENT In all calls to date, ARG3 is instantiated as 
          (COMPARE-26  POSSIBLE-NAME-OF-CLASS-RELNS-22 ELEMENT-RELNS-15))
    (AND ARG1 ARG2 ARG3))

(COMMENT POSSIBLE-NAME-OF-CLASS-OBJECTS-20 is not a BEING yet; it may never become one)
(COMMENT ELEMENT-OBJECTS-11 is not a BEING yet; it may never become one)

MOVE CURSOR TO  COMPARE-26 TYPE OF  COMPARE
PUP: Sorry to bother you, but I can no longer defer this DICHOTOMY decision:
	To compare two objects, we may apply a function directly to them.
	Alternatively, we might apply a function to corresponding pairs of subparts of
	the two objects, and finally join together all these sub-comparisons' results.
	The two objects to be compared are POSSIBLE-NAME-OF-CLASS-RELNS-22 and ELEMENT-RELNS-15.
	AHA!!!! I'VE RESOLVED IT MYSELF!!! NO NEED TO INTERACT WITH THE SLOW USER
        CHANNEL AFTER ALL!!! Based on the known structures of the two objects, I 
	see that alternative (2) about comparing subparts makes more sense. 
	Tentatively, I am going to define COMPARE-26 as the following:
  (PROGN 
     (COMMENT Here we may later want to put some assignments, rewrites, iterative statements)
     (COND ((NOT (FORSOME RELATION IN POSSIBLE-NAME-OF-CLASS-RELNS-22
                             (RECOGNIZE:# RELATION ELEMENT-RELNS-15)))
                T)
               (T NIL)))
Many of the BEINGs mentioned want to specialize themselves.

MOVE CURSOR TO  CONTRADICTS-27 TYPE OF  RECOGNIZE:#
PUP: Sorry to bother you, but I can no longer defer this SOMEOF decision:
	Contradiction occurs with an entity whose probability of presence was supposed
	to be: exactly 1, exactly 0, or inside the open interval (0,1).
	Since the decision is Some-of, just type any ordered subset of A,B,C, where
	(A .... PROBABILITY=1:#)
	(B .... PROBABILITY=0:#)
	(C .... PROBABILITY>0&<1:#)
USER: \2(A B C)\*


(I recommend that POSSIBLE-NAME-OF-CLASS-RELNS-22 be structured into these 3 pieces:
  PROBABILITY=1:#-PART-OF-POSSIBLE-NAME-OF-CLASS-RELNS-22
  PROBABILITY=0:#-PART-OF-POSSIBLE-NAME-OF-CLASS-RELNS-22 
  PROBABILITY>0&<1:#-PART-OF-POSSIBLE-NAME-OF-CLASS-RELNS-22.
Please reply Yes, No, Details, or Unsure: \2Yes\*

\7        <The Long-Name-Demon now grumbles about these 3 awkward names.>\*
PUP: I want a shorter name for PROBABILITY-1:#-PART-OF-POSSIBLE-NAME-OF-CLASS-RELNS.
USER: \2YES-RELNS\*
PUP: The name chosen is YES-RELNS-28
 .
 .
 .

CONTRADICTS-27 is filled in as:  
(LAMBDA (ARG1 ARG2)
   (COMMENT In all calls to date, ARG1 is instantiated as RELATION)
   (COMMENT In all calls to date, ARG2 is instantiated as ELEMENT-RELNS-15)
   (COND
      ((MEMBER ARG1 YES-RELNS-28)
        (COMMENT ARG1 occurs with probability 1, so it had better be in ARG2,
		       which is the relevant piece of the world)
        (NOT (MEMBER ARG1 ARG2)))
      ((MEMBER ARG1 NO-RELNS-29)
	(COMMENT Since ARG1 should never be present, we have a contradiction iff it is a
		       member of ARG2, the relevant piece of the world)
        (MEMBER ARG1 ARG2))
      (T (COMMENT We may or may not have ARG1 in ARG2; either case is allowable here,
		      so we never have a contradiction)
        NIL)))

PUP: I worked to clarify some unusual situation, namely (In all code generated,
	    POSSIBLE-NAME-OF-CLASS-RELNS-22 should be replaced by
	    (APPEND YES-RELNS-28 NO-RELNS-29 MAYBE-RELNS-30)),
	and here is what I finally did about it: (I replaced all occurrences as above).

MOVE CURSOR TO  MODIFY-STRUCTURE-7 TYPE OF  MODIFY-STRUCTURE
PUP: Sorry to bother you, but I can no longer defer this SUBSETOF decision:
	We can modify the structure by inserting, deleting, or altering existing members.
	Since the decision is Some-of, type an ordered subset of A,B,C, where
	(A .... CONDITIONAL-INSERTION)
	(B .... CONDITIONAL-DELETION)
	(C .... COMPLEX-ALTERATION)
USER: \2(A C)\*
PUP: In that case, the args and meta-code of MODIFY-7 are filled in as:
  (LAMBDA (ARG1)
    (COMMENT In all calls to date, ARG1 is instantiated as NAME-OF-CLASS)
    (COMMENT In all calls to date, ARG2 is instantiated as NIL)
    (CONDITIONAL-INSERTION-31 ARG1 ARG2)
    (COMPLEX-ALTERATION-32 ARG1 ARG2)))

PUP: I have decided to keep POSSIBLE-NAME-OF-CLASS structured using the PROPERTY LIST
	 feature of LISP. For this reason, I need to have a name for each property
 	 (corresponding to each subpart of POSSIBLE-NAME-OF-CLASS) :

\7This is the end of the example fragments of dialogue\*

\1**********************************************************************\*


.FILL
.SELECT 7
.ONCE TURN ON "{}"
Below is the same piece of dialogue set off by lines of asterisks on
page {EPAGE}. It occupied only seven lines of the preceding excerpt, but
below it occupies eight ⊗4pages.⊗* The user may interrupt after each BEING
receives control, and often does. When in an interrupt,
the user is prompted by ⊗2REQUEST:⊗*, after which he may type in a 
query. This will typically be the name of a BEING part, which is then
"asked" of the current BEING.  The active BEINGs are kept on a stack,
and typing CH will print out this stack. Typing OLDER or YOUNGER lets
the user crawl around this stack; the question he types in is by default
put to the BEING indicated by the stack marker (when printed, this BEING
name is surrounded by asterisks). 
.SELECT 6
.NOFILL

INTERRUPT? \2YES
\*REQUEST: \2CH
\*NIL *** CHOOSE-FROM *** (WRITE-PROGRAM SERVE)
.BEGIN FILL SELECT 7
This last request, CH, asked PUP6 to type out the control history;
who called who, etc.  In the current case, this is simply a stack.
The present BEING is CHOOSE-FROM, and it is delimited by asterisks.
It was called by WRITE-PROGRAM which was called by SERVE.
.END
REQUEST: \2WHAT
\*(Choose the best BEING from this set of BEINGS: 
				       OBTAIN-USABLE-INFORMATION 
				       USE-INFORMATION
				       FILL-IN-UNDEFINED-SECTION
				       CLARIFY-IMPROBABLE-SITUATION
			 	       ADAPT-PRECONCEIVED-FUNCTION
				       FIX-INCORRECT-PIECE)

REQUEST: \2WHY
\*(Because the flow of control of a program must be determinate)

REQUEST: \2OLDER        \* \7That is, which BEING called this one?
\*WRITE-PROGRAM

REQUEST: \2CH
\*(CHOOSE-FROM) *** WRITE-PROGRAM *** (SERVE)  \7Notice we are now pointing to WRITE-PROGRAM\*

REQUEST: \2WHAT  \*  \7When we ask this, we are asking WRITE-PROGRAM, not CHOOSE-FROM anymore.\*
(Write a program which does (CONCEPT-FORMATION))

REQUEST: \2WHY
\*(Fundamental drive to obey user; Also, it is necessary that code be written to do
	(CONCEPT-FORMATION) in order that the task of concept formation might be
	successfully accomplished; Also, I suggest you examine SPEC-WHY part of me)

REQUEST: \2SPEC-WHY
\*(We call the first BEING who claims he can bring about the effect:
 			(TYPE OF CONCEPT-FORMATION HAS BEEN STUDIED))

REQUEST: \2HOW
\*(Create specialized LISP code which will do (CONCEPT-FORMATION))

REQUEST: \2?\* \7This lists all the questions the user may ask during aninterrupt
\*
 YOUR OPTIONS ARE AS FOLLOWS:

QUIT    END THE INTERRUPT
BEING   PRINT NAME OF CURRENT BEING
DEMONS  PRINT SET OF DEMONS CURRENTLY ACTIVE
CONTROL-HISTORY    PRINT LIST OF BEINGS IN CONTROL, THE PATH FROM THE
                   CURRENT BEING BACK TO THE BEGINNING OF THE PROGRAM
OLDER   CONSIDER THE BEING WHICH CALLED THE CURRENT ONE
YOUNGER CONSIDER THE BEING WHICH THE CURRENT ONE CALLED
OLDEST  CONSIDER THE FIRST BEING IN CONTROL
YOUNGEST    CONSIDER THE LAST BEING IN CONTROL 
SPEC-WHEN   AN EVALUATED VERSION OF 'WHEN'
FAIL   END THE INTERRUPT AND CAUSE CURRENT BEING TO FAIL
NEW-LEVEL   CHANGE THE USER-INTERRUPT LEVEL
SPEC-WHY   PRINT OUT THE SPECIFIC REASON(S) THAT THIS BEING WAS

Typing one of these will print out WRITE-PROGRAM'S answer to that question:
 (IDEN IMPLICIT-ARGS EXPLICIT-ARGS EXPLICIT-ARGS-CHECK NLAMBDA 
  NON-EVAL-ARGS WHAT HOW WHY SPEC-WHY MAIN-EFFECTS MINOR-EFFECTS WHEN 
  META-CODE COMMENTS PRE-REQUISITES CO-REQUISITES POST-REQUISITES DEMONS 
  AFFECTS COMPLEXITY-VECTOR GENERALIZATIONS SPECIALIZATIONS
  ALTERNATIVES PREDICATE DATA-STRUCTURE ENCODABLE 
  INHIBIT-CURRENT-DEMONS FORM-CHANGING)

REQUEST: \2SPEC-WHEN
\*(Feature 1 is the program T. We evaluate it and get T. So the weight must be added in.
	The weight program for this feature is
		(COND ((MEMBER TASK ABLE-PUP-LIST) -75) (T 40)) 
	We evaluate it and get the value 40. The explanation for this feature is:
		(Because a pre-existing ability to do concept formation implies that
		writing a new program to accomplish it is superfluous, and, conversely,
		the inability to do concept formation abductively encourages us that
		we are in fact on the right track by writing a new program for it.
 Feature 2 is the program (MEMBER TASK WRITTEN-PROGRAMS-LIST). We evaluate it and get
	NIL. So the weight is not added in. The weight would have been -80.
 Feature 3 is the program:
	 ((MEMBER ( PUP IS ABOUT TO WRITE A PROGRAM TO DO (TASK)) AWARE-USER-LIST)
	We evaluate it and get the value NIL. So we don't add in the weight,
	which would have been +70.
 Feature 4 is the program T. We evaluate it and get T. So we do add in the weight. The
	program for the weight is (COND (NEW-INFO-LIST -120) (T 40)). We evaluate it
	and get the weight +40. The explanation is (Because if no new information is
        present, then we needn't feel guilty about starting to write a program).
 There are no more features. We add the relevant weights 40, 40, and the final WHEN value is:
 80)
.SELECT 6

REQUEST: \2CH
\*(CHOOSE-FROM) *** WRITE-PROGRAM *** (SERVE)

REQUEST: \2OLDER    \* \7That is, who called WRITE-PROGRAM?
\*SERVE

REQUEST: \2CH   \* \7Notice we are now pointing to that oldest BEING, SERVE
\*(CHOOSE-FROM WRITE-PROGRAM) *** SERVE *** NIL

REQUEST: \2WHAT \* \7We are asking SERVE what he does
\*(Do anything the user asks)

REQUEST: \2WHY
\*(Fundamental drive to serve the user)

REQUEST: \2HOW
\*(Get a task from the user)

REQUEST: \2QUIT \* \7End the interrupt; continue processing.

\*INTERRUPT? \2YES \* \7Apparently, CHOOSE-FROM has transferred control to someone.

\*REQUEST: \2BEING\*   \7Who has control now?
\*BETTER    \7i.e., the name of the BEING now in control is "BETTER"\*

REQUEST: \2WHAT \* \7This question is assumed to be directd to the BEING named BETTER
\*(Decide which of (USE-INFORMATION 'PGM) and  (OBTAIN USABLE INFORMATION 'PGM) is
	more a propos to try)

REQUEST: \2WHY
\*(I can only try at most one of USE-INFORMATION and OBTAIN-USABLE-INFORMATION at a time)

REQUEST: \2HOW
\*(Compare the WHEN parts of USE-INFORMATION and OBTAIN-USABLE-INFORMATION, and,
	if necessary, compare their COMPLEXITY VECTORS)

REQUEST: \2COMPLEXITY-VECTOR
\*(.5 .5 .5 .5 .1)

REQUEST: \2CH
\*NIL *** BETTER *** (CHOOSE-FROM WRITE-PROGRAM SERVE)
.BEGIN FILL SELECT 7
Thus CHOOSE-FROM has called BETTER hierarchically. In fact, CHOOSE-FROM simply
is a loop, wherein the current best alternative is compared to the next one on the list
of alternatives, using the function BETTER.
.END

REQUEST: \2QUIT

\*INTERRUPT? \2NO
\*INTERRUPT? \2NO
\*INTERRUPT? \2NO
\*INTERRUPT? \2YES

\*REQUEST: \2WHAT   \* \7What is going on now?
\*(Satisfy the simple subgoal (TYPE OF CONCEPT-FORMATION HAS BEEN STUDIED))

REQUEST: \2HOW
\*(Pass control to the simplest sufficient BEING)

REQUEST: \2AFFECTS    \* \7Who might be affected, and how?
\*((STUDY-TYPE might be called, with argument set to (CONCEPT-FORMATION)
  (TRY-BEING will be called)
  (SORT will be called)
  (A-BEING-ORDER will be called))

REQUEST: \2CH
\*NIL *** SATISFY *** (FILL-IN-UNDEFINED-SECTION CHOOSE-FROM 
							  WRITE-PROGRAM SERVE)

REQUEST: \2OLDER
\*FILL-IN-UNDEFINED-SECTION

REQUEST: \2WHAT
\*(Fill in an undefined section of code and add it to the program PGM for CF)

REQUEST: \2WHY
\*(Because all pieces of code must be defined or the program wont run)

REQUEST: \2HOW \* \7How, in general, does this Fill-in-undefined-section BEING work?
\*(Choose the simplest undefined piece and encode it)

REQUEST: \2CHOICE  \* \7In ths case, what was that BEING's choice of a piece to fill in?
\*( CF-1 TYPE OF ( CONCEPT-FORMATION)) \7Not surprising, since that is all that's known!\*

REQUEST: \2QUIT

\*INTERRUPT? \2YES

\*REQUEST: \2BEING
\*REINVESTIGATE-DECISION

REQUEST: \2WHAT
\*(Resolve the decision 
     (BOOLEAN (Subject-specific behavior may be required of CF-1)
      AFFECTS (Whether parameters describing an individual must be read in by CF-1)
      WHEN (Before any routines are finalized)
      WHY (Because any processing routine may have to depend upon some indiv. parameters))
   Must resolve it now because 
	(SETINTERSECTION UNDEFINED-SECTION-LIST DOING-PUP-LIST) is no longer Null.
   I should first try to defer this decision a little longer)

REQUEST: \2HOW
\*(Try to defer until ????; else try to resolve it with present knowledge; as a last
	resort, ask the user to resolve it)

REQUEST: \2QUIT

\*INTERRUPT? \2YES

\*REQUEST: \2CH
\*NIL *** DEFER-DECISION *** (REINVESTIGATE-DECISION 
	FILL-IN-UNDEFINED-SECTION CHOOSE-FROM WRITE-PROGRAM SERVE)
\7It should be clear from the HOW part of REINVESTIGATE-DECISION why it first calls on DEFER\*

REQUEST: \2QUIT

\*INTERRUPT? \2YES

\*REQUEST: \2CH
\*NIL *** UTILIZE *** (WHEN-NEXT DEFER-DECISION REINVESTIGATE-DECISION 
			   FILL-IN-UNDEFINED-SECTION CHOOSE-FROM WRITE-PROGRAM SERVE)
\* \7In order to defer, we try to find when next we actuallt will use the result of the
decision. In order to find this out, we must utilize some general programming knowledge.\*

REQUEST: \2HOW
\*(Search through the subset NIL of programming knowledge for applicable rules)
\7<i.e., there are no known ways to defer this any longer>\*

REQUEST: \2QUIT

\*INTERRUPT? \2YES

\*REQUEST: \2CH
\*NIL *** RESOLVE-DECISION *** (DEFER-DECISION REINVESTIGATE-DECISION 
				 FILL-IN-UNDEFINED-SECTION CHOOSE-FROM 
				 WRITE-PROGRAM SERVE)

REQUEST: \2WHY   \* \7Why are you trying to resolve it now?
\*(As far as we know at this instant, the decision 
     (BOOLEAN (SUBJECT-SPECIFIC BEHAVIOR MAY BE REQUIRED OF CF-1) )
   cannot be deferred any longer)

REQUEST: \2HOW
\*(Try to resolve (BOOLEAN (SUBJECT-SPECIFIC BEHAVIOR MAY BE REQUIRED OF CF-1))
	with present knowledge; if that fails, then I will ask the user about it)

REQUEST: \2QUIT

\*INTERRUPT? \2YES

\*REQUEST: \2BEING\*
ASK-USER-ABOUT  \7Thus it appears that we can't resolve it without asking the user\*

REQUEST: \2WHAT
\*(Ask the user to resolve the decision)

REQUEST: \2WHY
\*(Because I cannot resolve it, but it must be resolved at this time)

REQUEST: \2QUIT
\*

MOVE CURSOR TO  CF-1 TYPE OF  CONCEPT-FORMATION

PUP: Sorry to bother you, but I can no longer defer this Boolean type of decision:
    (SUBJECT-SPECIFIC BEHAVIOR MAY BE REQUIRED OF CF-1)
    Should I discuss ramifications? \2Yes\*
PUP: Affirmative: ths would force CF to mimic different human subjects.
		This would be done by reading in parameters for each individual.
		I can't wait because every part of CF would then be parameterized.
	Negative: In this case, there would be no action to take.
        Since the decision is Boolean, just answer Yes, No, Unsure, or Details: \2No\*
  PUP: Nothing need be done now. I am ready to move on.

\1**********************************************************************

.ONCE TURN ON "{}"
This concludes the expansion of the example in the box on page {EPAGE}.
Here are a few more direct queries to BEINGS during the dialogue:\*

REQUEST: \2UNDEFINED-SECTION-LIST
\*( PAD-2 TYPE OF ( PARTITION-A-DOMAIN))

REQUEST: \2AWARE-USER-LIST
\*((The name of the program to do  CONCEPT-FORMATION  is  CF-1)
(PUP & User may refer to this new specialized version of CONCEPT-FORMATION as CF-1)

REQUEST: \2(PLUS 2 2)\* 
4
.BEGIN FILL SELECT 7
The evaluation inside an interrupt is converse to DWIM: 
if the expression can be understood, it is processed specially; 
otherwise, we THEN try to EVAL the expression.
.END

REQUEST: \2DEMONS
\*THE CURRENT DEMONS ARE:
       (FRINGE-OF-CONCIOUSNESS-DEMON PSYCHOLOGY-DEMON 
	PROGRAM-WRITING-DEMONS DEFERRAL-DEMON 
	REINVESTIGATION-DEMON IDIOM-DEMON
	SPECIFICITY-CHECK-DEMON FORGETFUL-USER-DEMON))

REQUEST: \2NEW-LEVEL\* \7This is how we adjust the frequency of the interrupts
\*
Hello.  I am ready to switch to a different mode of interruptability.
How often should I let you interrupt me, to ask me about what I', doing?
	Type a single digit, as explained below:
		 0  NEVER (ULTIMATE PRODUCTION-RUN MODE)
		 2  A COUPLE OF TIMES DURING THE COURSE OF WRITING A PROGRAM
		 4  DURING EACH PHASE OF WRITING A PROGRAM
		 6  DURING THE WRITING OF EACH NONTRIVIAL SUBFUNCTION OF A PROGRAM
		 8  DURING EACH PHASE OF WRITING EACH SUBFUNCTION OF A PROGRAM
		10  EACH TIME A BEING TRANSFERS CONTROL (ULTIMATE DEBUG MODE)
	OK, now type a digit... \2NO\*
***  ERROR  ***     You MUST type one even integer from 0 TO 10 inclusive. Try again:
\28\*   
OK, That's better.

REQUEST: \2QUIT
\*

.FILL

\3This concludes the "frequent-interrupt mode" excerpt. In the terminology
of NEW-LEVEL, this was at interrupt level 10, while the earlier excerpts
were at level 0.  Recall that this last excerpt was but seven lines in the
earlier excerpt, which in turn was only 3% of the actual 300-page dialogue.
The reader who has read through to this point will probably agree that
dialogue problems are central
to automatic programming.\*
.EVERY HEADING(,,)
.PORTION CONTENTS
.NOFILL
.BEGIN CENTER


⊗5 KNOWLEDGE AS COOPERATING EXPERTS:  ↓_ BEINGS_↓⊗*




⊗2Douglas B. Lenat

Stanford Artificial Intelligence Laboratory
Stanford, California⊗*


.END
.PREFACE 10 MILLS
.TURN ON "{∞→"
.NARROW 11,11
.SKIP 2
.RECEIVE

.ONCE CENTER
⊗7{DATE}